إعادة ترتيب التلاعب قليلا

Question

أحتاج إلى إجراء إعادة ترتيب عشوائي لقيمة 7 بت (نعم، أعلم أنني يجب أن أستخدم جدولًا) وأتساءل عما إذا كان هناك أي اختراقات للقيام بذلك.

مثال:

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6>

// the naive way
out =
   (0x020 & In) << 5 |
   (0x008 & In) << 2 |
   (0x040 & In)      |
   (0x012 & In) >> 1 |
   (0x004 & In) >> 2 |
   (0x001 & In) >> 3;

// 6 ANDs, 5 ORs, 5 shifts = 16 ops

---

يحرر:كنت أفكر في شيء على غرار هذا

فقط من أجل الركلات ولأنني كنت AFTK أحاول البحث بقوة عن حلول النموذج:

((In * C1) >> C2) & 0x7f

لم يتم العثور على حلول.

Answer 1

ألق نظرة على مخرجات المترجم للكود "الساذج" الخاص بك، فقد يفاجئك.لقد فعلت شيئًا من هذا القبيل ذات مرة وقام المترجم (VC++ 2005) بتغيير قيم جميع قيم ands وshifts بالكامل بالنسبة لي لجعلها أكثر كفاءة، على سبيل المثال، أنا متأكد من أنه سيزيل "(0x001 & In) >> 3".

لكن نعم، إذا كان التعديل الوزاري عبارة عن وظيفة ثابتة، فمن المحتمل أن يكون الجدول هو الأفضل.

تحديث

من أجل الضحك نظرت إلى مخرجات المترجم من VC++ 2005....

أولاً قمت بتجربة قيمة ثابتة لـ "In" لكن المترجم لم ينخدع ولو بت واحد، فقد أنتج هذا الكود:

mov eax,469h

أي.لقد قام بتحسينه بالكامل.

لذا ...لقد حاولت إدخالًا مناسبًا وحصلت على هذا:

00401D4F  mov         eax,ecx 
00401D51  and         eax,20h 
00401D54  shl         eax,3 
00401D57  mov         edx,ecx 
00401D59  and         edx,8 
00401D5C  or          eax,edx 
00401D5E  mov         edx,ecx 
00401D60  sar         edx,1 
00401D62  and         edx,2 
00401D65  or          edx,ecx 
00401D67  sar         edx,1 
00401D69  shl         eax,2 
00401D6C  and         edx,9 
00401D6F  or          eax,edx 
00401D71  and         ecx,40h 
00401D74  or          eax,ecx 

هذه أربع عمليات تحويل، وخمس عمليات AND، وأربع عمليات تشغيل - وهذا ليس سيئًا بالنسبة لستة مدخلات.ربما أفضل مما يمكن أن يفعله معظم الناس باليد.

من المحتمل أيضًا أن يكون مُحسّنًا للتنفيذ خارج الترتيب، لذا ستكون دورات الساعة أقل مما تبدو.:-)

Answer 2

والخطوة الأولى يبدو أن لفهم الحل الرياضي وتحسين ذلك.

ونرى هنا من الخارقة قليلا

Answer 3

وهناك الكثير من الخارقة بت twiddling لعمليات مشتركة، أي إلى عكس ترتيب البتات في كلمة 32 بت (10 لكل منهما من التحول، ووOR، AFAICR).

في هذه الحالة، مع مخطط يبدو تعسفيا تماما من مدخلات الانتاج، لا أستطيع أن أرى أي طريقة لتنظيف هذا الأمر.

استخدم جدول بحث:)

Answer 4

وقبل على النحو الأمثل، يجب عليك التأكد من طريقك "ساذجة" تفعل ما كنت تنوي. إذا قمت بعمل التعليمات البرمجية في وظيفة وتشغيل هذه الحلقة:

for (b=0;b<7;b++)
{
    i=1<<b;
    printf("%d: %02x -> %02x\n", b, i, shuffle(i));
}

ووتنتج هذا الإخراج، الذي يتناقض مع التعليقات. في الواقع، فإنه يفقد بت.

0: 01 -> 00
1: 02 -> 01
2: 04 -> 01
3: 08 -> 20
4: 10 -> 08
5: 20 -> 00
6: 40 -> 40

في أجل الحصول على خلط تصفون، وأود أن رمز مثل هذا:

   //    0 1 2 3 4 5 6 
   //-> 3 2 4 1 5 0 6
   (0x001 & In) << 3 |
   (0x004 & In) << 2 |
   (0x020 & In)      |
   (0x012 & In) << 1 |
   (0x008 & In) >> 2 |
   (0x020 & In) >> 5 ;