كيفية القيام بإضافة تشبع غير موقعة في لغة C؟

Question

ما هي أفضل طريقة (أنظف وأكثر كفاءة) لكتابة إضافة مشبعة في لغة C؟

يجب أن تقوم الدالة أو الماكرو بإضافة مدخلين غير موقعين (يحتاجان إلى الإصدارين 16 و32 بت) وإرجاع البتات بالكامل (0xFFFF أو 0xFFFFFFFF) في حالة تجاوز المجموع.

الهدف هو x86 وARM باستخدام gcc (4.1.2) وVisual Studio (للمحاكاة فقط، لذلك لا بأس بالتنفيذ الاحتياطي هناك).

Answer 1

ربما تريد المحمولة C الكود هنا، والذي سيحوله المترجم الخاص بك إلى تجميع ARM مناسب.لدى ARM تحركات مشروطة، ويمكن أن تكون مشروطة بالتجاوز.تصبح الخوارزمية بعد ذلك إضافة، وتعيين الوجهة بشكل مشروط على غير موقعة (-1) إذا تم اكتشاف تجاوز السعة.

uint16_t add16(uint16_t a, uint16_t b)
{
  uint16_t c = a + b;
  if (c<a) /* Can only happen due to overflow */
    c = -1;
  return c;
}

لاحظ أن هذا يختلف عن الخوارزميات الأخرى من حيث أنه يصحح التجاوز، بدلاً من الاعتماد على عملية حسابية أخرى للكشف عن التجاوز.

إخراج x86-64 clang 3.7 -O3 لـ add32:أفضل بكثير من أي إجابة أخرى:

    add     edi, esi
    mov     eax, -1
    cmovae  eax, edi
    ret

أرم الإصدار 7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm الإخراج لads32:

    adds    r0, r0, r1      @ c, a, b
    it      cs
    movcs   r0, #-1         @ conditional-move
    bx      lr

16 بت:لا يزال لا يستخدم تعليمات الإضافة غير المشبعة غير الموقعة الخاصة بـ ARM (UADD16)

    add     r1, r1, r0        @ tmp114, a
    movw    r3, #65535      @ tmp116,
    uxth    r1, r1  @ c, tmp114
    cmp     r0, r1    @ a, c
    ite     ls        @
    movls   r0, r1        @,, c
    movhi   r0, r3        @,, tmp116
    bx      lr  @

Answer 2

في عادي ج:

uint16_t sadd16(uint16_t a, uint16_t b)
    { return (a > 0xFFFF - b) ? 0xFFFF : a + b; }

uint32_t sadd32(uint32_t a, uint32_t b)
    { return (a > 0xFFFFFFFF - b) ? 0xFFFFFFFF : a + b;} 

وهو تقريبًا ماكرو وينقل المعنى مباشرة.

Answer 3

في IA32 بدون قفزات مشروطة:

uint32_t sadd32(uint32_t a, uint32_t b)
{
#if defined IA32
  __asm
  {
    mov eax,a
    xor edx,edx
    add eax,b
    setnc dl
    dec edx
    or eax,edx
  }
#elif defined ARM
  // ARM code
#else
  // non-IA32/ARM way, copy from above
#endif
}

Answer 4

في ARM قد يكون لديك بالفعل حساب مشبع مدمج.يمكن لامتدادات ARMv5 DSP تشبع السجلات بأي طول بت.عادةً ما يكون تشبع ARM أيضًا رخيصًا لأنه يمكنك تنفيذ معظم التعليمات المشروطة.

يحتوي ARMv6 أيضًا على عمليات جمع وطرح مشبعة وجميع الأشياء الأخرى لـ 32 بت وأرقام معبأة.

على x86 تحصل على حساب مشبع إما عبر MMX أو SSE.

كل هذا يحتاج إلى أداة تجميع، لذا فهو ليس ما طلبته.

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

يتم ذلك أولاً.ثم يتم حساب حالات الحمل وإضافتها واستبدالها بقناع في حالة تجاوز الإضافة.

uint32_t SatAddUnsigned8(uint32_t x, uint32_t y) 
{
  uint32_t signmask = 0x80808080;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 7);
  return (x ^ t0) | t1;
}

يمكنك الحصول على نفس الشيء بالنسبة لـ 16 بت (أو أي نوع من حقول البت) عن طريق تغيير ثابت قناع الإشارة والتحولات في الأسفل مثل هذا:

uint32_t SatAddUnsigned16(uint32_t x, uint32_t y) 
{
  uint32_t signmask = 0x80008000;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 15);
  return (x ^ t0) | t1;
}

uint32_t SatAddUnsigned32 (uint32_t x, uint32_t y)
{
  uint32_t signmask = 0x80000000;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 31);
  return (x ^ t0) | t1;
}

الكود أعلاه يفعل نفس الشيء بالنسبة لقيم 16 و32 بت.

إذا لم تكن بحاجة إلى الميزة التي تضيفها الوظائف وتشبع قيمًا متعددة بالتوازي، فما عليك سوى إخفاء البتات التي تحتاجها.في ARM، تريد أيضًا تغيير ثابت قناع الإشارة لأن ARM لا يمكنه تحميل جميع ثوابت 32 بت الممكنة في دورة واحدة.

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

Answer 5

إذا كنت تهتم بالأداء، فأنت حقًا تريد أن تفعل هذا النوع من الأشياء في SIMD، حيث يحتوي x86 على حساب مشبع أصلي.

وبسبب هذا النقص في الحساب المشبع في الرياضيات العددية، يمكن للمرء أن يحصل على حالات تكون فيها العمليات التي تتم على SIMD ذات 4 متغيرات أكثر أسرع بـ 4 مرات من المكافئ C (وبالمثل صحيح مع SIMD ذو 8 متغيرات):

sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks

Answer 6

حل الفرع صفر:

uint32_t sadd32(uint32_t a, uint32_t b)
{
    uint64_t s = (uint64_t)a+b;
    return -(s>>32) | (uint32_t)s;
}

سيقوم المترجم الجيد بتحسين ذلك لتجنب القيام بأي عملية حسابية فعلية 64 بت (s>>32 سيكون مجرد العلم الذي يحمله، و -(s>>32) إنه نتيجة ل sbb %eax,%eax).

في x86 asm (بناء جملة AT&T، a و b في eax و ebx, ، يؤدي الى eax):

add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax

يجب أن تكون الإصدارات 8 و16 بت واضحة.قد تتطلب النسخة الموقعة المزيد من العمل.

Answer 7

uint32_t saturate_add32(uint32_t a, uint32_t b)
{
    uint32_t sum = a + b;
    if ((sum < a) || (sum < b))
        return ~((uint32_t)0);
    else
        return sum;
} /* saturate_add32 */

uint16_t saturate_add16(uint16_t a, uint16_t b)
{
    uint16_t sum = a + b;
    if ((sum < a) || (sum < b))
        return ~((uint16_t)0);
    else
        return sum;
} /* saturate_add16 */

يحرر: الآن بعد أن قمت بنشر نسختك، لست متأكدًا من أن نسختي أكثر نظافة/أفضل/أكثر كفاءة/أكثر دراسة.

Answer 8

لست متأكدًا مما إذا كان هذا أسرع من حل Skizz (الملف الشخصي دائمًا)، ولكن إليك حل بديل للتجميع بدون فرع.لاحظ أن هذا يتطلب تعليمات النقل المشروط (CMOV)، والتي لست متأكدًا من توفرها على هدفك.

uint32_t sadd32(uint32_t a, uint32_t b)
{
    __asm
    {
        movl eax, a
        addl eax, b
        movl edx, 0xffffffff
        cmovc eax, edx
    }
}

Answer 9

التنفيذ الحالي الذي نستخدمه هو:

#define sadd16(a, b)  (uint16_t)( ((uint32_t)(a)+(uint32_t)(b)) > 0xffff ? 0xffff : ((a)+(b)))
#define sadd32(a, b)  (uint32_t)( ((uint64_t)(a)+(uint64_t)(b)) > 0xffffffff ? 0xffffffff : ((a)+(b)))

Answer 10

عادةً ما يتضمن الأداء الأفضل التجميع المضمن (كما ذكر البعض بالفعل).

لكن بالنسبة للغة C المحمولة، تتضمن هذه الوظائف مقارنة واحدة فقط ولا تتضمن اختيار النوع (وبالتالي أعتقد أنها الأمثل):

unsigned saturate_add_uint(unsigned x, unsigned y)
{
    if (y>UINT_MAX-x) return UINT_MAX;
    return x+y;
}

unsigned short saturate_add_ushort(unsigned short x, unsigned short y)
{
    if (y>USHRT_MAX-x) return USHRT_MAX;
    return x+y;
}

كوحدات ماكرو، فإنها تصبح:

SATURATE_ADD_UINT(x, y) (((y)>UINT_MAX-(x)) ? UINT_MAX : ((x)+(y)))
SATURATE_ADD_USHORT(x, y) (((y)>SHRT_MAX-(x)) ? USHRT_MAX : ((x)+(y)))

أترك إصدارات "غير موقعة طويلة" و"طويلة غير موقعة" كتمرين للقارئ.؛-)

Answer 11

فقط في حالة رغبة شخص ما في معرفة التنفيذ دون التفرع باستخدام الأعداد الصحيحة 32 بت المكملة لـ 2.

تحذير!يستخدم هذا الرمز العملية غير المحددة:"shift right بمقدار -1" وبالتالي يستغل خاصية تعليمات إنتل بنتيوم سال لإخفاء معامل العد إلى 5 بت.

int32_t sadd(int32_t a, int32_t b){
    int32_t sum = a+b;
    int32_t overflow = ((a^sum)&(b^sum))>>31;
    return (overflow<<31)^(sum>>overflow);
 }

إنه أفضل تنفيذ عرفته

Answer 12

أفترض أن أفضل طريقة لـ x86 هي استخدام المجمّع المضمن للتحقق من علامة تجاوز السعة بعد الإضافة.شيء مثل:

add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......

انها ليست محمولة للغاية، ولكن IMHO هي الطريقة الأكثر فعالية.

Answer 13

البديل لحل asm x86 المجاني للفرع هو (بناء جملة AT&T، a وb في eax وebx، يؤدي إلى eax):

add %eax,%ebx
sbb $0,%ebx

Answer 14

باستخدام C++، يمكنك كتابة نسخة أكثر مرونة من ريمو.دالحل :

template<typename T>
T sadd(T first, T second)
{
    static_assert(std::is_integral<T>::value, "sadd is not defined for non-integral types");
    return first > std::numeric_limits<T>::max() - second ? std::numeric_limits<T>::max() : first + second;
}

يمكن ترجمة ذلك بسهولة إلى لغة C - باستخدام الحدود المحددة في limits.h.يرجى أيضًا ملاحظة أن أنواع الأعداد الصحيحة ذات العرض الثابت قد لا تكون متاحة على النظام الخاص بك.

Answer 15

//function-like macro to add signed vals, 
//then test for overlow and clamp to max if required
#define SATURATE_ADD(a,b,val)  ( {\
if( (a>=0) && (b>=0) )\
{\
    val = a + b;\
    if (val < 0) {val=0x7fffffff;}\
}\
else if( (a<=0) && (b<=0) )\
{\
    val = a + b;\
    if (val > 0) {val=-1*0x7fffffff;}\
}\
else\
{\
    val = a + b;\
}\
})

لقد أجريت اختبارًا سريعًا ويبدو أنه نجح، لكن لم أقم بتخريبه على نطاق واسع حتى الآن!هذا يعمل مع التوقيع 32 بت.المرجع :المحرر المستخدم في صفحة الويب لا يسمح لي بنشر ماكرو، أي أنه لا يفهم بناء الجملة بدون مسافة بادئة وما إلى ذلك!

Answer 16

int saturating_add(int x, int y)
{
    int w = sizeof(int) << 3;
    int msb = 1 << (w-1);

    int s = x + y;
    int sign_x = msb & x;
    int sign_y = msb & y;
    int sign_s = msb & s;

    int nflow = sign_x && sign_y && !sign_s;
    int pflow = !sign_x && !sign_y && sign_s;

    int nmask = (~!nflow + 1);
    int pmask = (~!pflow + 1);

    return (nmask & ((pmask & s) | (~pmask & ~msb))) | (~nmask & msb);
}

لا يستخدم هذا التطبيق تدفقات التحكم، ومشغلي Campare(==, !=) و ال ?: المشغل أو العامل.إنه يستخدم فقط عوامل البت والعوامل المنطقية.

Answer 17

حساب التشبع ليس معيارًا للغة C، ولكن غالبًا ما يتم تنفيذه عبر جوهر المترجم، وبالتالي فإن الطريقة الأكثر كفاءة لن تكون الأنظف.يجب عليك إضافة #ifdef كتل لتحديد الطريقة الصحيحة.إجابة MSalters هي الأسرع في بنية x86.لـ ARM تحتاج إلى استخدامه __qadd16 وظيفة (مترجم ARM). _arm_qadd16 (مايكروسوفت فيجوال ستوديو) للإصدار 16 بت و __qadd لإصدار 32 بت.سيتم ترجمتها تلقائيًا إلى تعليمات ARM واحدة.

الروابط:

• __qadd16
• _arm_qadd16
• __qadd