كيفية تحويل مجموعة من البايتات بمقدار 12 بت

Question

أريد نقل محتويات مصفوفة من البايتات بمقدار 12 بت إلى اليسار.

على سبيل المثال، البدء بهذا المصفوفة من النوع uint8_t shift[10]:

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0A, 0xBC}

أرغب في تحويله إلى اليسار بمقدار 12 بت مما يؤدي إلى:

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xAB, 0xC0, 0x00}

Answer 1

مرحى للمؤشرات!

يعمل هذا الرمز من خلال التطلع إلى 12 بت لكل بايت ونسخ البتات المناسبة للأمام.12 بت هو النصف السفلي (nybble) من البايت التالي والنصف العلوي من 2 بايت.

unsigned char length = 10;
unsigned char data[10] = {0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0A,0xBC};
unsigned char *shift = data;
while (shift < data+(length-2)) {
    *shift = (*(shift+1)&0x0F)<<4 | (*(shift+2)&0xF0)>>4;
    shift++;
}
*(data+length-2) = (*(data+length-1)&0x0F)<<4;
*(data+length-1) = 0x00;

كتب جوستين:
@ مايك، الحل الخاص بك يعمل، لكنه لا يعمل.

حسنًا، أود أن أقول إن عملية التحول العادية تفعل ذلك تمامًا (وتسمى الفائض)، وتسمح فقط للبتات الإضافية بالسقوط من اليمين أو اليسار.إنه أمر بسيط بما يكفي لحمله إذا أردت ذلك - ما عليك سوى حفظ الـ 12 بت قبل البدء في النقل.ربما تريد تحولًا دائريًا، لإعادة الأجزاء الفائضة إلى الأسفل؟ربما تريد إعادة تخصيص المصفوفة وجعلها أكبر؟إعادة الفائض إلى المتصل؟إرجاع قيمة منطقية في حالة تجاوز سعة البيانات غير الصفرية؟يجب عليك تحديد ما يعنيه الحمل بالنسبة لك.

unsigned char overflow[2];
*overflow = (*data&0xF0)>>4;
*(overflow+1) = (*data&0x0F)<<4 | (*(data+1)&0xF0)>>4;
while (shift < data+(length-2)) {
    /* normal shifting */
}  
/* now would be the time to copy it back if you want to carry it somewhere */
*(data+length-2) = (*(data+length-1)&0x0F)<<4 | (*(overflow)&0x0F);
*(data+length-1) = *(overflow+1);  

/* You could return a 16-bit carry int, 
 * but endian-ness makes that look weird 
 * if you care about the physical layout */
unsigned short carry = *(overflow+1)<<8 | *overflow;

Answer 2

هذا هو الحل الذي أقترحه، ولكن الأهم من ذلك هو أسلوبي في حل المشكلة.

لقد اقتربت من المشكلة

• رسم خلايا الذاكرة ورسم الأسهم من الوجهة إلى المصدر.
• قمت بعمل جدول يوضح الرسم أعلاه.
• تسمية كل صف في الجدول بعنوان البايت النسبي.

هذا أظهر لي النمط:

• يترك iL يكون الحد الأدنى (نصف بايت) من a[i]
• يترك iH يكون القضم عالية من a[i]
• iH = (i+1)L
• iL = (i+2)H

يحمل هذا النمط كافة البايتات.

الترجمة إلى لغة C تعني:

a[i] = (iH << 4) OR iL
a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4)

والآن نتقدم بثلاث ملاحظات أخرى:

• وبما أننا ننفذ المهام من اليسار إلى اليمين، فلن نحتاج إلى تخزين أي قيم في متغيرات مؤقتة.
• سيكون لدينا حالة خاصة للذيل:الجميع 12 bits في النهاية سيكون صفراً.
• يجب علينا تجنب قراءة الذاكرة غير المحددة بعد المصفوفة.لأننا لم نقرأ أبدًا أكثر من a[i+2], ، وهذا يؤثر فقط على البايتتين الأخيرتين

لذلك، نحن

• التعامل مع الحالة العامة عن طريق التكرار لـ N-2 bytes وإجراء الحساب العام أعلاه
• التعامل مع البايت التالي إلى الأخير من خلال الإعداد iH = (i+1)L
• التعامل مع البايت الأخير عن طريق ضبطه على 0

منح a مع الطول N, ، نحن نحصل:

for (i = 0; i < N - 2; ++i) {
    a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4);
}
a[N-2] = (a[N-1) & 0x0f) << 4;
a[N-1] = 0;

وهناك لديك...يتم نقل المصفوفة إلى اليسار بمقدار 12 bits.ويمكن تعميمها بسهولة على التحول N bits, ، مشيراً إلى أنه سيكون هناك M بيانات المهمة حيث M = number of bits modulo 8, ، أعتقد.

يمكن جعل الحلقة أكثر كفاءة على بعض الأجهزة عن طريق ترجمتها إلى مؤشرات

for (p = a, p2=a+N-2; p != p2; ++p) {
    *p = ((*(p+1) & 0x0f) << 4) | (((*(p+2) & 0xf0) >> 4);
}

وباستخدام أكبر نوع بيانات صحيح تدعمه وحدة المعالجة المركزية.

(لقد كتبت هذا للتو، لذا سيكون الآن هو الوقت المناسب لشخص ما لمراجعة الكود، خاصة وأن التلاعب بالقليل من السهل أن يخطئ.)

Answer 3

دعونا نجعلها أفضل طريقة للتحول N بت في مجموعة من الأعداد الصحيحة 8 بت.

N            - Total number of bits to shift
F = (N / 8) - Full 8 bit integers shifted
R = (N % 8) - Remaining bits that need to be shifted

أعتقد أنه سيتعين عليك من هنا العثور على الطريقة المثلى للاستفادة من هذه البيانات للتنقل بين ints في المصفوفة.تتمثل الخوارزميات العامة في تطبيق إزاحات الأعداد الصحيحة الكاملة من خلال البدء من يمين المصفوفة وتحريك كل عدد صحيح F الفهارس.صفر ملء المساحات الفارغة حديثا.ثم أخيرًا قم بإجراء R تحول البت على جميع الفهارس، بدءًا من اليمين مرة أخرى.

في حالة التحول 0xBC بواسطة R بت يمكنك حساب الفائض عن طريق إجراء عملية AND والإزاحة باستخدام عامل النقل bitshift:

// 0xAB shifted 4 bits is:
(0xAB & 0x0F) >> 4   // is the overflow      (0x0A)
0xAB << 4            // is the shifted value (0xB0)

ضع في اعتبارك أن البتات الأربعة هي مجرد قناع بسيط:0x0F أو فقط 0b00001111.من السهل حساب ذلك، أو إنشائه ديناميكيًا، أو حتى يمكنك استخدام جدول بحث ثابت بسيط.

وآمل أن يكون عاما بما فيه الكفاية.أنا لست جيدًا في استخدام C/C++ على الإطلاق، لذا ربما يستطيع شخص ما تنظيف بناء الجملة الخاص بي أو أن يكون أكثر تحديدًا.

علاوة:إذا كنت ماهرًا في استخدام لغة C، فقد تتمكن من تزوير فهارس مصفوفة متعددة في عدد صحيح واحد 16 أو 32 أو حتى 64 بت وإجراء التحولات.لكن هذا ليس محمولاً للغاية وأود أن أوصي بعدم القيام بذلك.مجرد التحسين ممكن.

Answer 4

إليك حل عملي باستخدام المتغيرات المؤقتة:

void shift_4bits_left(uint8_t* array, uint16_t size)
{
    int i;
    uint8_t shifted = 0x00;    
    uint8_t overflow = (0xF0 & array[0]) >> 4;

    for (i = (size - 1); i >= 0; i--)
    {
        shifted = (array[i] << 4) | overflow;
        overflow = (0xF0 & array[i]) >> 4;
        array[i] = shifted;
    }
}

قم باستدعاء هذه الدالة 3 مرات لإزاحة 12 بت.

قد يكون حل مايك أسرع، بسبب استخدام المتغيرات المؤقتة.

Answer 5

النسخة 32 بت...:-) يعالج 1 <= count <= num_words

#include <stdio.h>

unsigned int array[] = {0x12345678,0x9abcdef0,0x12345678,0x9abcdef0,0x66666666};

int main(void) {
  int count;
  unsigned int *from, *to;
  from = &array[0];
  to = &array[0];
  count = 5;

  while (count-- > 1) {
    *to++ = (*from<<12) | ((*++from>>20)&0xfff);
  };
  *to = (*from<<12);

  printf("%x\n", array[0]);
  printf("%x\n", array[1]);
  printf("%x\n", array[2]);
  printf("%x\n", array[3]);
  printf("%x\n", array[4]);

  return 0;
}

Answer 6

@ جوزيف، لاحظ أن عرض المتغيرات هو 8 بت، بينما يبلغ عرض الإزاحة 12 بت.الحل الخاص بك يعمل فقط مع N <= حجم متغير.

إذا كان بإمكانك افتراض أن المصفوفة الخاصة بك هي من مضاعفات الرقم 4، فيمكنك تحويل المصفوفة إلى مصفوفة uint64_t ثم العمل على ذلك.إذا لم يكن من مضاعفات 4، فيمكنك العمل في أجزاء 64 بت على أكبر قدر ممكن والعمل على الباقي واحدًا تلو الآخر.قد يكون هذا أكثر تعقيدًا بعض الشيء، لكنني أعتقد أنه أكثر أناقة في النهاية.

Answer 7

هناك حالتان من الحالات التي تجعل هذه مشكلة رائعة:

• قد تكون مجموعة الإدخال فارغة
• تحتاج البتات الأخيرة وما قبل الأخيرة إلى معالجة خاصة، نظرًا لأنه لم يتم إزاحة أي بتات إليها

إليك حل بسيط يتكرر فوق المصفوفة لنسخ القضمة ذات الترتيب المنخفض من البايتة التالية إلى القضمة ذات الترتيب العالي، والقضم عالي الترتيب من البايتة التالية (+2) إلى القضمة ذات الترتيب المنخفض.لحفظ إلغاء مرجعية مؤشر النظرة الأمامية مرتين، فإنه يحتفظ بمخزن مؤقت مكون من عنصرين مع البايتات "الأخيرة" و"التالية":

void shl12(uint8_t *v, size_t length) {
  if (length == 0) {
    return; // nothing to do
  }

  if (length > 1) {
    uint8_t last_byte, next_byte;
    next_byte = *(v + 1);

    for (size_t i = 0; i + 2 < length; i++, v++) {
      last_byte = next_byte;
      next_byte = *(v + 2);
      *v = ((last_byte & 0x0f) << 4) | (((next_byte) & 0xf0) >> 4);
    }

    // the next-to-last byte is half-empty
    *(v++) = (next_byte & 0x0f) << 4;
  }

  // the last byte is always empty
  *v = 0;
}

خذ بعين الاعتبار الحالات الحدودية، التي تقوم بتنشيط أجزاء أكثر من الوظيفة على التوالي:

• متى length هو صفر، نحن ننقذ دون لمس الذاكرة.
• متى length هو واحد، وضعنا العنصر الواحد والوحيد على الصفر.
• متى length اثنان، قمنا بتعيين القضم عالي الترتيب للبايت الأول على القضم ذو الترتيب المنخفض للبايت الثاني (أي البتات 12-16)، والبايت الثاني على الصفر.نحن لا نقوم بتنشيط الحلقة.
• متى length أكبر من اثنين، قمنا بتنفيذ الحلقة، مع تبديل البايتات عبر المخزن المؤقت المكون من عنصرين.

إذا كانت الكفاءة هي هدفك، فربما تعتمد الإجابة إلى حد كبير على بنية جهازك.عادةً، يجب عليك الحفاظ على المخزن المؤقت المكون من عنصرين، ولكن التعامل مع كلمة الآلة (عدد صحيح غير موقّع 32/64 بت) في المرة الواحدة.إذا كنت تقوم بنقل الكثير من البيانات، فسيكون من المفيد التعامل مع البايتات القليلة الأولى كحالة خاصة حتى تتمكن من جعل مؤشرات الكلمات الآلية الخاصة بك محاذاة للكلمات.تصل معظم وحدات المعالجة المركزية إلى الذاكرة بشكل أكثر كفاءة إذا كانت عمليات الوصول تقع على حدود الكلمات الآلية.بالطبع، يجب التعامل مع البايتات الزائدة بشكل خاص أيضًا حتى لا تلمس الذاكرة بعد نهاية المصفوفة.