Adler-32

از ویکیپدیا، دانشنامه آزاد
پرش به ناوبری پرش به جستجو

Adler-32 یک الگوریتم کنترلی است که توسط مارک آدلر در سال 1995 نوشته شده است، [1] که جمع چک فلچر را اصلاح می کند . در مقایسه با یک بررسی افزونگی چرخه‌ای با همان طول، قابلیت اطمینان را با سرعت معامله می‌کند (ترجیح دومی). Adler-32 قابل اعتمادتر از Fletcher-16 و کمی کمتر از Fletcher-32 است. [2]

تاریخچه

چک‌سوم Adler-32 بخشی از کتابخانه فشرده سازی zlib است که به طور گسترده مورد استفاده قرار می‌گیرد ، زیرا هر دو توسط مارک آدلر توسعه یافته‌اند . یک نسخه " rolling checksum " Adler-32 در ابزار rsync استفاده می شود.

محاسبه

یک جمع کنترلی Adler-32 با محاسبه دو جمع 16 بیتی A و B و الحاق بیت های آنها به یک عدد صحیح 32 بیتی به دست می آید. A مجموع تمام بایت های جریان به اضافه یک است و B مجموع مقادیر جداگانه A از هر مرحله است.

در ابتدای اجرای Adler-32، A به 1، B به 0 مقداردهی اولیه می شود. مجموع ها با مدول 65521 (بزرگترین عدد اول کوچکتر از 2 16 ) انجام می شود. بایت ها به ترتیب شبکه ذخیره می شوند ( اندیان بزرگB که دو بایت مهم را اشغال می کند.

تابع ممکن است به صورت بیان شود

A = 1 + D 1 + D 2 + ... + D n (mod 65521)

B = (1 + D 1 ) + (1 + D 1 + D 2 ) + ... + (1 + D 1 + D 2 + ... + D n ) (mod 65521)
  = n × D 1 + ( n -1) × D 2 + ( n -2) × D 3 + ... + D n + n (mod 65521)

Adler-32 ( D ) = B × 65536 + A

که در آن D رشته بایت هایی است که جمع چک برای آن ها محاسبه می شود و n طول D است.

مثال

مجموع Adler-32 رشته ASCIIWikipedia " " به صورت زیر محاسبه می شود:

شخصیت کد اسکی آ ب
(نشان داده شده به عنوان پایه 10)
دبلیو 87 1 + 87 = 88 0 + 88 = 88
من 105 88 + 105 = 193 88 + 193 = 281
ک 107 193 + 107 = 300 281 + 300 = 581
من 105 300 + 105 = 405 581 + 405 = 986
پ 112 405 + 112 = 517 986 + 517 = 1503
ه 101 517 + 101 = 618 1503 + 618 = 2121
د 100 618 + 100 = 718 2121 + 718 = 2839
من 105 718 + 105 = 823 2839 + 823 = 3662
آ 97 823 + 97 = 920 3662 + 920 = 4582
A = 920 = 0x398 (پایه 16)
B = 4582 = 0x11E6
خروجی = 0x11E6 << 16 + 0x398 = 0x11E60398 = 300286872

عملیات مدول در این مثال هیچ تاثیری نداشت، زیرا هیچ یک از مقادیر به 65521 نرسید.

مقایسه با چک جمع فلچر

اولین تفاوت بین این دو الگوریتم این است که مجموع Adler-32 با مدول یک عدد اول محاسبه می شوند، در حالی که مجموع فلچر با مدول 2 4 −1، 2 8 −1 یا 2 16 −1 (بسته به تعداد بیت های استفاده شده) محاسبه می شوند. که همگی اعداد مرکب هستند . استفاده از یک عدد اول این امکان را برای Adler-32 ایجاد می‌کند تا تفاوت‌هایی را در ترکیب خاصی از بایت‌ها که فلچر قادر به تشخیص آن نیست، بیابد.

تفاوت دوم که بیشترین تأثیر را بر سرعت الگوریتم دارد، این است که مجموع Adler بر روی بایت‌های 8 بیتی به جای کلمات 16 بیتی محاسبه می‌شود و در نتیجه تعداد تکرارهای حلقه دو برابر می‌شود. این باعث می‌شود که جمع کنترلی Adler-32 بین یک و نیم تا دو برابر مدت زمان بررسی فلچر برای داده‌های تراز شده کلمات ۱۶ بیتی طول بکشد. برای داده های بایت تراز شده، Adler-32 سریع تر از چک جمع فلچر است که به درستی پیاده سازی شده است (به عنوان مثال، یکی که در قالب داده های سلسله مراتبی یافت می شود ).

اجرای نمونه

در C ، یک پیاده سازی ناکارآمد اما ساده به صورت زیر است:

const uint32_t MOD_ADLER = 65521 ;    

uint32_t adler32 ( char unsigned * data , size_t len ​​) /*     که در آن داده ها محل داده ها در حافظه فیزیکی و     len طول داده ها بر حسب بایت است */      




{
    uint32_t a = 1 , b = 0 ;      
    اندازه_t شاخص ; 
    
    // هر بایت داده را به ترتیب 
پردازش کنید ( شاخص = 0 ؛ شاخص < len ؛ شاخص ++ )           
    {
        a = ( a + داده [ نمایه ]) % MOD_ADLER ;      
        b = ( b + a ) % MOD_ADLER ;      
    }
    
    بازگشت ( b << 16 ) | یک _     
}

کد منبع zlib را برای اجرای کارآمدتر که نیاز به واکشی و دو اضافه در هر بایت دارد، با عملیات مدول به تعویق افتاده با دو باقیمانده محاسبه شده در هر چند هزار بایت، ببینید، تکنیکی که برای اولین بار برای جمع‌های چک فلچر در سال 1988 کشف شد. js-adler32بهینه‌سازی مشابهی را ارائه می‌کند. افزودن ترفندی که محاسبه "15" را در 65536 - 65521 به تاخیر می اندازد تا مدول ها سریعتر شوند: می توان نشان داد که ((a >> 16) * 15 + (a & 65535)) % 65521معادل انباشت ساده است. [3]

مزایا و معایب

  • مانند CRC-32 استاندارد ، Adler-32 checksum را می توان به راحتی جعل کرد و بنابراین برای محافظت در برابر تغییرات عمدی ناامن است.
  • در بسیاری از پلتفرم ها از CRC-32 سریعتر است. [4]
  • Adler-32 برای پیام‌های کوتاه با چند صد بایت ضعف دارد، زیرا جمع‌های کنترلی این پیام‌ها پوشش ضعیفی از 32 بیت موجود دارند.

ضعف

Adler-32 برای پیام های کوتاه ضعیف است زیرا مجموع A جمع نمی شود. حداکثر مجموع یک پیام 128 بایتی 32640 است که کمتر از مقدار 65521 است که توسط عملیات مدول استفاده می شود، به این معنی که تقریباً نیمی از فضای خروجی استفاده نشده است و توزیع در قسمت مورد استفاده غیریکنواخت است. توضیح گسترده ای را می توان در RFC  3309 یافت ، که استفاده از CRC32C را به جای Adler-32 برای SCTP ، پروتکل انتقال کنترل جریان، الزامی می کند. [5] همچنین نشان داده شده است که Adler-32 برای تغییرات کوچک افزایشی ضعیف است، [6] و همچنین برای رشته های تولید شده از یک پیشوند مشترک و اعداد متوالی ضعیف است (مانند نام برچسب های تولید شده به طور خودکار توسط مولدهای کد معمولی).[7]

همچنین ببینید

یادداشت ها

  1. «اولین ظهور Adler-32 (به ChangeLog و adler32.c مراجعه کنید)» .
  2. «بازدید از چک‌سام‌های فلچر و آدلر» (PDF) .
  3. «adler32.js» . ورق JS. 3 جولای 2019.
  4. ترزا سی ماکسینو، فیلیپ جی. کوپمن (ژانویه 2009). "اثربخشی جمع های کنترلی برای شبکه های کنترل جاسازی شده" (PDF) . تراکنش های IEEE در محاسبات قابل اعتماد و ایمن .
  5. ^ RFC 3309 
  6. "Cbloom rants: 08-21-10 - Adler32" . 21 آگوست 2010.
  7. ^ "توابع هش: مقایسه تجربی - strchr.com" . www.strchr.com .

پیوندهای خارجی