لطالما تساءلت عن كيفية ضغط البيانات ، بما في ذلك في ملفات مضغوطة. بمجرد أن قررت إشباع فضولي: لمعرفة كيفية عمل الضغط ، وكتابة برنامج Zip الخاص بي. أصبح التنفيذ ممارسة مثيرة في البرمجة. تحصل على متعة كبيرة من إنشاء آلة مصححة تأخذ البيانات ، وتنقل بتاتها إلى تمثيل أكثر كفاءة ، ثم تجمعها مرة أخرى. آمل أن تكون مهتمًا أيضًا بالقراءة عنه.تشرح المقالة بتفصيل كبير كيف تعمل ملفات Zip ونظام الضغط: ضغط LZ77 ، خوارزمية هوفمان ، خوارزمية الانكماش والمزيد. سوف تتعلم تاريخ تطور التكنولوجيا وتنظر في أمثلة التنفيذ الفعالة إلى حد ما المكتوبة من الصفر في C. شفرة المصدر هنا: hwzip-1.0.zip .وأنا ممتن جدا ل أنج البرتيني ، Gynvael Coldwind ، فابيان جيسين ، جوناس Skeppstedt ( على شبكة الإنترنت )، Primiano توتشى، و نيكو ويبر ، الذين قدموا ملاحظات قيمة على مسودات من هذه المادة.المحتوى
قصة
PKZip
في الثمانينيات وأوائل التسعينات ، قبل انتشار الإنترنت ، استخدم هواة الكمبيوتر أجهزة مودم الاتصال الهاتفي للاتصال عبر شبكة الهاتف بشبكة أنظمة لوحة الإعلانات (BBS). BBS هو نظام كمبيوتر تفاعلي يسمح للمستخدمين بإرسال الرسائل وممارسة الألعاب ومشاركة الملفات. للاتصال بالإنترنت ، كان يكفي أن يكون لديك جهاز كمبيوتر ومودم ورقم هاتف BBS جيد. تم نشر الأرقام في مجلات الكمبيوتر وعلى BBS أخرى.كانت أداة هامة لتسهيل توزيع ملفات أرشيفي . يسمح لك بحفظ ملف واحد أو أكثر في ملف أرشيف واحدلتخزين المعلومات أو نقلها بشكل أكثر ملاءمة. وبشكل مثالي ، يقوم الأرشيف أيضًا بضغط الملفات لتوفير المساحة والوقت للإرسال عبر الشبكة. في أيام BBS ، كان أرشيفي Arc شائعًا ، كتبه توم هندرسون من شركة System Enhancement Associates (SEA) ، وهي شركة صغيرة أسسها مع صهره.في أواخر الثمانينيات ، أصدر المبرمج فيل كاتز نسخته الخاصة من Arc ، PKArc. كانت متوافقة مع SEA Arc ، لكنها عملت بشكل أسرع بفضل الروتينات الفرعية المكتوبة بلغة التجميع واستخدمت طريقة ضغط جديدة. أصبح البرنامج شائعًا ، واستقال كاتز من وظيفته وخلق PKWare للتركيز على مزيد من التطوير. وفقا للأسطورة ، تم معظم العمل في مطبخ والدته في جليندال ، ويسكونسن.تصوير فيل كاتز من مقال نشر في ميلووكي سينتينل ، 19 سبتمبر 1994.ومع ذلك ، لم يحب SEA مبادرة كاتز. اتهمته الشركة بانتهاك العلامات التجارية وحقوق التأليف والنشر. أصبح التقاضي والجدل على شبكة BBS وعالم الكمبيوتر الشخصي معروفًا باسم Arc Wars . في النهاية ، تم تسوية النزاع لصالح SEA.التخلي عن Arc ، أنشأ Katz تنسيق أرشفة جديد في عام 1989 ، والذي أطلق عليه Zip وأتاحه للجمهور :, , , . , ".ZIP", , , , , , , , , .
كان برنامج كاتز لإنشاء مثل هذه الملفات يسمى PKZip وسرعان ما انتشر إلى عالم BBS والكمبيوتر الشخصي.أحد الجوانب التي ساهمت على الأرجح في نجاح تنسيق Zip هو أن الوثائق جاءت مع PKZip ، ملاحظة التطبيق ، والتي تشرح بالتفصيل كيفية عمل التنسيق. سمح هذا للآخرين بتعلم التنسيق وإنشاء البرامج التي تنشئ ملفات Zip أو تستخرجها أو تتفاعل معها بأي طريقة أخرى.Zip - تنسيق ضغط بدون فقد : بعد تفريغ البيانات ستكون كما كانت قبل الضغط. تسعى الخوارزمية إلى التكرار في بيانات المصدر وتقدم معلومات أكثر كفاءة. هذا النهج يختلف عن الضغط مع الفقد .، والتي يتم استخدامها في تنسيقات مثل JPEG و MP3: عند ضغطها ، يتم التخلص من بعض المعلومات الأقل وضوحًا للعين أو الأذن البشرية.تم توزيع PKZip كـ Shareware: يمكن استخدامه ونسخه بحرية ، لكن المؤلف اقترح على المستخدمين "تسجيل" البرنامج. مقابل 47 دولارًا ، يمكنك الحصول على تعليمات مطبوعة ودعم متميز وإصدار محسّن من التطبيق.كان أحد الإصدارات الرئيسية لـ PKZip 2.04c ، الذي صدر في 28 ديسمبر 1992 (تم إصدار الإصدار 2.04g بعد فترة وجيزة ). يستخدم خوارزمية ضغط الانكماش الافتراضية. حددت النسخة التطوير الإضافي للضغط في ملفات Zip ( مقالة مخصصة للإصدار ).منذ ذلك الحين ، تم استخدام تنسيق zip في العديد من تنسيقات الملفات الأخرى. على سبيل المثال ، تستخدم أرشيفات Java (.jar) وحزم تطبيقات Android (.apk) وملفات Microsoft Office .docx تنسيق Zip. تستخدم العديد من التنسيقات والبروتوكولات نفس خوارزمية الضغط ، Deflate. لنفترض على الأرجح أن صفحات الويب يتم نقلها إلى متصفحك كملف gzip ، والذي يستخدم تنسيقه ضغط الانكماش.توفي فيل كاتز في عام 2000. لا يزال PKWare موجودًا ويدعم تنسيق Zip ، على الرغم من أن الشركة تركز بشكل أساسي على برامج حماية البيانات.Info-zip و zlib
بعد وقت قصير من إصدار PKZip في عام 1989 ، بدأت تظهر برامج أخرى لتفريغ ملفات Zip. على سبيل المثال ، برنامج unzip يمكنه فك الحزم على أنظمة Unix. في مارس 1990 ، تم إنشاء قائمة بريدية تسمى Info-ZIP.على معلومات-ZIP مجموعة أصدرت برامج مفتوحة المصدر مجانية بفك و الرمز البريدي ، والتي كانت تستخدم لتفريغ وإنشاء الملفات المضغوطة. تم نقل الرمز إلى العديد من الأنظمة ، ولا يزال المعيار لبرامج Zip لأنظمة Unix. وقد ساعد ذلك لاحقًا على زيادة شعبية الملفات المضغوطة.بمجرد نقل رمز Info-ZIP الذي قام بفك ضغط الضغط وإلغاء ضغطه إلى مكتبة zlib منفصلة كتبوهاجان لوب جيللي (ضغط) ومارك أدلر (تفريغ).جان لوب جيللي (يسار) ومارك أدلر (يمين) في جائزة USENIX STUG لعام 2009.أحد أسباب إنشاء المكتبة هو أنها وفرت الراحة لاستخدام ضغط Deflate في التطبيقات والتنسيقات الأخرى ، على سبيل المثال ، في gzip الجديد و PNG . كان القصد من هذه التنسيقات الجديدة استبدال Compress و GIF ، التي استخدمت خوارزمية LZW المحمية ببراءة اختراع.كجزء من إنشاء هذه التنسيقات ، كتب بيتر دويتش مواصفات الانكماش ونشرها تحت اسم Internet RFC 1951 في مايو 1996. وقد تبين أن هذا وصف أكثر سهولة مقارنة بملاحظة تطبيق PKZip الأصلية.اليوم يستخدم zlib في كل مكان. ربما هو الآن مسؤول عن ضغط هذه الصفحة على خادم الويب وتفريغها في متصفحك. اليوم ، يتم ضغط معظم الملفات المضغوطة وفك ضغطها باستخدام zlib.Winzip
استخدم العديد من أولئك الذين لم يجدوا PKZip WinZip. تحول مستخدمو الكمبيوتر الشخصي من DOS إلى Windows ، ومن PKZip إلى WinZip.بدأ كل شيء بمشروع للمبرمج Nico Mac ، الذي قام بإنشاء برنامج لـ OS / 2 في Mansfield Software Group في Storrs-Mansfield ، كونيتيكت. استخدم Nico مدير العروض التقديمية ، وهي واجهة مستخدم رسومية في OS / 2 ، وكان منزعجًا من أنه اضطر إلى التبديل من مدير الملفات إلى أوامر DOS في كل مرة يريد فيها إنشاء ملفات Zip.كتب Mac برنامج واجهة المستخدم الرسومية البسيط الذي عمل مع ملفات Zip مباشرة في Presentation Manager ، وأطلق عليه PMZip ، وأطلقه كبرنامج تجريبي في التسعينيات.لم ينجح OS / 2 ، وسيطر عالم الكمبيوتر على Microsoft Windows. في عام 1991 ، قرر Mac تعلم كيفية كتابة برامج Windows ، وكان أول مشروع له هو نقل تطبيق Zip إلى نظام تشغيل جديد. في أبريل 1991 ، تم إصدار WinZip 1.00 . تم توزيعه كبرنامج تجريبي مع فترة تجريبية لمدة 21 يومًا ورسوم تسجيل قدرها 29 دولارًا. بدت مثل هذا:في الإصدارات الأولى من WinZip ، تم استخدام PKZip تحت غطاء المحرك. ولكن من الإصدار 5.0 في عام 1993 ، بدأ استخدام التعليمات البرمجية من Info-ZIP للمعالجة المباشرة لملفات Zip. كما تطورت واجهة المستخدم تدريجيًا.WinZip 6.3 ضمن Windows 3.11 لمجموعات العمل.كان WinZip واحدًا من برامج التشفير الأكثر شعبية في التسعينات. ولكن في النهاية ، فقد أهميته بسبب تضمين دعم لملفات Zip في أنظمة التشغيل. يعمل Windows معهم كـ "مجلدات مضغوطة" منذ عام 2001 (Windows XP) ، وتستخدم مكتبة DynaZip لهذا الغرض.كان Mac يسمى في الأصل Nico Mak Computing. في عام 2000 ، أعيدت تسميته WinZip Computing ، وفي تلك السنوات تركه ماك. في عام 2005 ، قامت Vector Capital ببيع الشركة، وفي النهاية ، أصبحت مملوكة لشركة Corel ، التي لا تزال تطلق WinZip كمنتج.ضغط Lempel-Ziv (LZ77)
يتكون ضغط Zip من مكونين رئيسيين: ضغط Lempel-Ziv ورمز Huffman.تتمثل إحدى طرق ضغط النص في إنشاء قائمة بالكلمات أو العبارات الشائعة مع استبدال أصناف هذه الكلمات داخل النص بروابط إلى القاموس. على سبيل المثال ، يمكن تمثيل الكلمة الطويلة "ضغط" في النص المصدر بالرقم # 1234 ، حيث يشير 1234 إلى موضع الكلمة في القائمة. وهذا ما يسمى ضغط القاموس .ولكن من وجهة نظر الضغط الشامل ، فإن هذه الطريقة لها عدة عيوب. أولاً ، ما الذي يجب أن يدخل القاموس بالضبط؟ يمكن أن تكون البيانات المصدر بلغات مختلفة ، حتى أنها لا يمكن أن تكون نصًا يمكن قراءته بواسطة الإنسان. وإذا لم يتم الاتفاق على القاموس مسبقًا بين الضغط وفك الضغط ، فيجب تخزينه ونقله مع البيانات المضغوطة ، مما يقلل من فائدة الضغط.الحل الأنيق لهذه المشكلة هو استخدام البيانات المصدر نفسها كمعجم. في عام 1977 ، اقترح خوارزمية عالمية لضغط البيانات المتسلسلة ، يعقوب زيف وأبراهام ليمبل (الذين عملوا في التخنيون) مخطط ضغط يتم فيه تقديم بيانات المصدر على أنها تسلسل ثلاثي:(, , )
حيث
أنها
تشكل حلقة الوراء لتسلسل الأحرف التي تريد نسخها من الموقف السابق في النص الأصلي، و
هذا هو الحرف التالي في البيانات التي تم إنشاؤها.إبراهيم لمبل ويعقوب زيف.خذ بعين الاعتبار السطور التالية:It was the best of times,
it was the worst of times,
في السطر الثاني ، يمكن تمثيل التسلسل "t was the w" على أنه (26 ، 10 ، w) ، حيث يتم إعادة إنشائه عن طريق نسخ 10 أحرف من موضع 26 حرفًا إلى الحرف "w". بالنسبة إلى الأحرف التي لم تظهر بعد ، يتم استخدام روابط خلفية ذات طول صفري. على سبيل المثال ، يمكن تمثيل الحرف "I" الأولي بالشكل (0 ، 0 ، I).يسمى هذا المخطط ضغط Lempel-Ziv ، أو ضغط LZ77. ومع ذلك ، في التطبيقات العملية للخوارزمية ، عادة لا يتم استخدام جزء من ثلاثية
. بدلاً من ذلك ، يتم إنشاء الأحرف بشكل فردي ، ويتم استخدام أزواج (
،
) للروابط الخلفية (يسمى هذا الخيار ضغط LZSS ). تُعد كيفية تشفير الأحرف والروابط الخلفية مشكلة منفصلة ، وسننظر فيها أدناه عندما نحلل الخوارزميةينكمش .هذا النص:It was the best of times,
it was the worst of times,
it was the age of wisdom,
it was the age of foolishness,
it was the epoch of belief,
it was the epoch of incredulity,
it was the season of Light,
it was the season of Darkness,
it was the spring of hope,
it was the winter of despair,
we had everything before us,
we had nothing before us,
we were all going direct to Heaven,
we were all going direct the other way
يمكنك الضغط في هذا:It was the best of times,
i(26,10)wor(27,24)age(25,4)wisdom(26,20)
foolishnes(57,14)epoch(33,4)belief(28,22)incredulity
(33,13)season(34,4)Light(28,23)Dark(120,17)
spring(31,4)hope(231,14)inter(27,4)despair,
we had everyth(57,4)before us(29,9)no(26,20)
we(12,3)all go(29,4)direct to Heaven
(36,28)(139,3)(83,3)(138,3)way
إحدى الخصائص المهمة للروابط الخلفية هي أنها يمكن أن تتداخل. يحدث هذا عندما يكون الطول أكبر من المسافة. على سبيل المثال:Fa-la-la-la-la
يمكنك الضغط من أجل:Fa-la(3,9)
قد يبدو الأمر غريبًا بالنسبة لك ، ولكن الطريقة تعمل: بعد نسخ وحدات البايت الثلاثة الأولى "-la" ، يستمر النسخ باستخدام وحدات البايت التي تم إنشاؤها حديثًا.في الواقع ، هذا هو نوع من ترميز أطوال السلسلة ، حيث يتم نسخ جزء من البيانات بشكل متكرر للحصول على الطول المطلوب.يظهر مثال تفاعلي لاستخدام ضغط Lempel-Ziv للكلمات في مقالة كتبها Colin Morris هل أصبحت كلمات البوب أكثر تكرارًا؟ .فيما يلي مثال لنسخ الروابط الخلفية في C. يرجى ملاحظة أنه بسبب التداخل المحتمل ، لا يمكننا استخدام memcpy
أو memmove
.
static inline void lz77_output_backref(uint8_t *dst, size_t dst_pos,
size_t dist, size_t len)
{
size_t i;
assert(dist <= dst_pos && "cannot reference before beginning of dst");
for (i = 0; i < len; i++) {
dst[dst_pos] = dst[dst_pos - dist];
dst_pos++;
}
}
من السهل إنشاء حرفي ، ولكن من أجل الاكتمال ، سنستخدم وظيفة مساعدة:
static inline void lz77_output_lit(uint8_t *dst, size_t dst_pos, uint8_t lit)
{
dst[dst_pos] = lit;
}
لاحظ أن المتصل بهذه الوظيفة يجب أن يتأكد من وجود dst
مساحة كافية للبيانات التي تم إنشاؤها وأن الارتباط الخلفي لا يصل إلى الموضع قبل بدء المخزن المؤقت.من الصعب عدم إنشاء بيانات باستخدام روابط خلفية أثناء التفريغ ، ولكن إنشاؤها أولاً عند ضغط بيانات المصدر. يمكن القيام بذلك بطرق مختلفة ، لكننا سنستخدم الطريقة القائمة على جداول التجزئة من zlib ، المقترحة في RFC 1951.سنستخدم جدول التجزئة مع مواضع البادئات المكونة من ثلاثة أحرف والتي تم العثور عليها سابقًا في السطر (الروابط الخلفية الأقصر لا تجلب أي فائدة). يسمح التفريغ للرابطات الخلفية ضمن الأحرف الـ 32،768 السابقة - وهذا ما يسمى النافذة. هذا يوفر ضغط الدفق: تتم معالجة بيانات الإدخال قليلاً في كل مرة ، بشرط أن يتم تخزين النافذة التي تحتوي على وحدات البايت الأخيرة في الذاكرة. ومع ذلك ، يفترض تنفيذنا أن جميع بيانات الإدخال متاحة لنا وأنه يمكننا معالجتها بالكامل في كل مرة. يتيح لك هذا التركيز على الضغط بدلاً من المحاسبة ، وهو أمر ضروري لمعالجة الدفق.سنستخدم صفيفين: في head
يحتوي على قيمة التجزئة للبادئة المكونة من ثلاثة أحرف للموضع في الإدخال ، وفي prev
يحتوي على موضع الموضع السابق بقيمة التجزئة هذه. في الواقع ، head[h]
هذا هو عنوان قائمة مرتبطة بمواضع البادئة بتجزئة h
، prev[x]
ويتلقى العنصر الذي يسبق x
القائمة.#define LZ_WND_SIZE 32768
#define LZ_MAX_LEN 258
#define HASH_SIZE 15
#define NO_POS SIZE_MAX
bool lz77_compress(const uint8_t *src, size_t len,
bool (*lit_callback)(uint8_t lit, void *aux),
bool (*backref_callback)(size_t dist, size_t len, void *aux),
void *aux)
{
size_t head[1U << HASH_SIZE];
size_t prev[LZ_WND_SIZE];
uint16_t h;
size_t i, j, dist;
size_t match_len, match_pos;
size_t prev_match_len, prev_match_pos;
for (i = 0; i < sizeof(head) / sizeof(head[0]); i++) {
head[i] = NO_POS;
}
لإدراج موضع سلسلة جديدة في جدول التجزئة prev
، يتم تحديثه للإشارة إلى المركز السابق head
، ثم يتم تحديثه بنفسه head
:static void insert_hash(uint16_t hash, size_t pos, size_t *head, size_t *prev)
{
prev[pos % LZ_WND_SIZE] = head[hash];
head[hash] = pos;
}
انتبه للعملية المعيارية عند الفهرسة prev
: نحن مهتمون فقط بالمواقف التي تقع في النافذة الحالية.بدلاً من حساب قيمة التجزئة لكل بادئة مكونة من ثلاثة أحرف من البداية ، سنستخدم التجزئة الدائري وسنقوم بتحديثها باستمرار بحيث لا تنعكس إلا قيمها الثلاثة الأخيرة:static uint16_t update_hash(uint16_t hash, uint8_t c)
{
hash <<= 5;
hash ^= c;
hash &= (1U << HASH_SIZE) - 1;
return hash;
}
يمكن بعد ذلك استخدام خريطة التجزئة للبحث بكفاءة عن التطابقات السابقة بتسلسل ، كما هو موضح أدناه. البحث عن التطابقات هو عملية الضغط الأكثر استخدامًا للموارد ، لذلك سنحد من عمق البحث في القائمة.يعد تغيير المعلمات المختلفة ، مثل عمق البحث في قائمة البادئات وإجراء مقارنات كسولة ، كما هو موضح أدناه ، طريقة لزيادة السرعة عن طريق تقليل درجة الضغط. يتم تحديد الإعدادات الموجودة في الكود الخاص بنا لتتوافق مع الحد الأقصى لمستوى الضغط في zlib.
static size_t find_match(const uint8_t *src, size_t pos, uint16_t hash,
size_t prev_match_len, size_t max_match_len,
const size_t *head, const size_t *prev,
size_t *match_pos)
{
size_t max_match_steps = 4096;
size_t i, l;
bool found;
if (prev_match_len == 0) {
prev_match_len = 2;
}
if (prev_match_len >= max_match_len) {
return 0;
}
if (prev_match_len >= 32) {
max_match_steps /= 4;
}
found = false;
i = head[hash];
while (max_match_steps != 0) {
if (i == NO_POS) {
break;
}
assert(i < pos && "Matches should precede pos.");
if (pos - i > LZ_WND_SIZE) {
break;
}
l = cmp(src, i, pos, prev_match_len, max_match_len);
if (l != 0) {
assert(l > prev_match_len);
assert(l <= max_match_len);
found = true;
*match_pos = i;
prev_match_len = l;
if (l == max_match_len) {
return l;
}
}
i = prev[i % LZ_WND_SIZE];
max_match_steps--;
}
if (!found) {
return 0;
}
return prev_match_len;
}
static size_t cmp(const uint8_t *src, size_t i, size_t j,
size_t prev_match_len, size_t max_match_len)
{
size_t l;
assert(prev_match_len < max_match_len);
for (l = 0; l < prev_match_len + 1; l++) {
if (src[i + prev_match_len - l] !=
src[j + prev_match_len - l]) {
return 0;
}
}
assert(l == prev_match_len + 1);
for (; l < max_match_len; l++) {
if (src[i + l] != src[j + l]) {
break;
}
}
assert(l > prev_match_len);
assert(l <= max_match_len);
assert(memcmp(&src[i], &src[j], l) == 0);
return l;
}
يمكنك إنهاء الوظيفة lz77_compress
بهذا الرمز للبحث عن التطابقات السابقة:
h = 0;
if (len >= 2) {
h = update_hash(h, src[0]);
h = update_hash(h, src[1]);
}
prev_match_len = 0;
prev_match_pos = 0;
for (i = 0; i + 2 < len; i++) {
h = update_hash(h, src[i + 2]);
match_len = find_match(src, i, h, prev_match_len,
min(LZ_MAX_LEN, len - i), head, prev,
&match_pos);
insert_hash(h, i, head, prev);
if (prev_match_len != 0 && prev_match_len >= match_len) {
dist = (i - 1) - prev_match_pos;
if (!backref_callback(dist, prev_match_len, aux)) {
return false;
}
for (j = i + 1; j < min((i - 1) + prev_match_len,
len - 2); j++) {
h = update_hash(h, src[j + 2]);
insert_hash(h, j, head, prev);
}
i = (i - 1) + prev_match_len - 1;
prev_match_len = 0;
continue;
}
if (match_len == 0) {
assert(prev_match_len == 0);
if (!lit_callback(src[i], aux)) {
return false;
}
continue;
}
if (prev_match_len != 0) {
if (!lit_callback(src[i - 1], aux)) {
return false;
}
}
prev_match_len = match_len;
prev_match_pos = match_pos;
}
if (prev_match_len != 0) {
dist = (i - 1) - prev_match_pos;
if (!backref_callback(dist, prev_match_len, aux)) {
return false;
}
i = (i - 1) + prev_match_len;
}
for (; i < len; i++) {
if (!lit_callback(src[i], aux)) {
return false;
}
}
return true;
}
يبحث هذا الرمز عن أطول رابط خلفي يمكن إنشاؤه في الموضع الحالي. ولكن قبل إصداره ، يقرر البرنامج ما إذا كان من الممكن العثور على تطابق أطول في الموضع التالي. في zlib ، يسمى هذا تقييم المقارنة البطيئة . لا تزال هذه خوارزمية جشعة : فهي تحدد أطول تطابق ، حتى إذا كانت الطريقة الأقصر الحالية تسمح لك بالحصول على مباراة أطول لفترة أطول وتحقيق ضغط أقوى.يمكن أن يعمل ضغط Lempel-Ziv بسرعة وبطيئة. Zopfliأمضى الكثير من الوقت في البحث عن روابط خلفية مثالية للضغط على نسب الضغط الإضافية. هذا مفيد للبيانات التي يتم ضغطها مرة واحدة ثم إعادة استخدامها ، على سبيل المثال ، للحصول على معلومات ثابتة على خادم الويب. على الجانب الآخر من المقياس توجد ضواغط مثل Snappy و LZ4 ، والتي تتم مقارنتها فقط مع البادئة 4 بايت الأخيرة وهي سريعة جدًا. يُعد هذا النوع من الضغط مفيدًا في قواعد البيانات وأنظمة RPC التي يتم فيها دفع الوقت المستغرق في الضغط عن طريق توفير الوقت عند إرسال البيانات عبر شبكة أو إلى قرص.إن فكرة استخدام بيانات المصدر كقاموس أنيقة للغاية ، ولكن يمكنك أيضًا الاستفادة من قاموس ثابت. Brotli هي خوارزمية تعتمد على LZ77 ، ولكنها تستخدم أيضًا خوارزمية كبيرةالقاموس الثابت للسلسلة ، والتي توجد غالبًا على الشبكة.ويمكن الاطلاع كود LZ77 في lz77.h و lz77.c .كود هوفمان
خوارزمية ضغط Zip الثانية هي رمز Huffman.إن مصطلح الكود في هذا السياق هو مرجع لنظام لتقديم البيانات في شكل آخر. في هذه الحالة ، نحن مهتمون بالكود الذي يمكن استخدامه لتمثيل الحرف والروابط الخلفية التي تم إنشاؤها بواسطة خوارزمية Lempel-Ziv بكفاءة.تقليديا ، يتم تقديم النص الإنجليزي باستخدام الكود القياسي الأمريكي لتبادل المعلومات (ASCII) . يعين هذا النظام رقمًا لكل حرف ، والذي يتم تخزينه عادة في تمثيل 8 بت. فيما يلي رموز ASCII للحروف الكبيرة من الأبجدية الإنجليزية:بايت واحد لكل حرف هو طريقة مناسبة لتخزين النص. يسمح لك بالوصول بسهولة أو تعديل أجزاء من النص ، ومن الواضح دائمًا عدد البايتات المطلوبة لتخزين الأحرف N ، أو عدد الأحرف المخزنة في N بايت. ومع ذلك ، هذه ليست الطريقة الأكثر فعالية من حيث المساحة المحتلة. على سبيل المثال ، في اللغة الإنجليزية ، يتم استخدام الحرف E في أغلب الأحيان ، و Z هو الأقل استخدامًا. لذلك ، من حيث الحجم ، من الأكثر فاعلية استخدام تمثيل بت أقصر لـ E وتمثيل أطول لـ Z ، بدلاً من تعيين نفس عدد البتات لكل حرف.الكود الذي يحدد الترميزات بأطوال مختلفة لأحرف المصدر المختلفة يسمى رمز متغير الطول . المثال الأكثر شهرة هو مورس.، حيث يتم ترميز كل حرف بنقاط وشرطات ، يتم إرسالها في الأصل عن طريق التلغراف مع نبضات قصيرة وطويلة:من عيوب شفرة مورس أن كلمة واحدة قد تكون بادئة لأخرى. على سبيل المثال ، • • - • لا يحتوي على فك تشفير فريد: يمكن أن يكون F أو ER. يتم حل ذلك عن طريق التوقف المؤقت (ثلاث نقاط في الطول) بين الحروف أثناء الإرسال. ومع ذلك ، سيكون من الأفضل إذا لم تكن كلمات الشفرة بادئات لكلمات أخرى. هذا الكود يسمى unrefixed . شفرة ASCII ذات الطول الثابت غير ثابتة لأن كلمات التشفير دائمًا ما تكون بنفس الطول. ولكن يمكن أيضًا إعادة إصلاح الرموز ذات الطول المتغير. غالبًا ما لا يتم إصلاح أرقام الهاتف. قبل إدخال رقم الطوارئ 112 في السويد ، كان يجب تغيير جميع الأرقام التي تبدأ بـ 112. وفي الولايات المتحدة الأمريكية ، لا يوجد رقم هاتف واحد يبدأ برقم 911.لتقليل حجم الرسالة المشفرة ، من الأفضل استخدام رمز غير مُعاد إصداره حيث يكون للأحرف التي تحدث بشكل متكرر كلمات شفرة أقصر. سيكون الرمز الأمثل هو الذي يولد أقصر نتيجة ممكنة - سيكون مجموع أطوال كلمات الشفرة ، مضروبًا في تكرار حدوثها ، هو الحد الأدنى الممكن. وهذا ما يسمى رمز غير بادئة مع الحد الأدنى من التكرار ، أو كود هوفمان ، تكريمًا لمخترع خوارزمية فعالة لتوليد مثل هذه الرموز.خوارزمية هوفمان
أثناء دراسة المواد لكتابة أطروحة الدكتوراه في الهندسة الإلكترونية في معهد ماساتشوستس للتكنولوجيا ، حضر ديفيد هوفمان دورة حول نظرية المعلومات قام بتدريسها روبرت فانو. وفقًا للأسطورة ، سمح Fano لطلابه بالاختيار: كتابة الاختبار النهائي أو الدورة التدريبية. اختار هوفمان الأخير ، وتم إعطاؤه موضوع البحث عن رموز غير مسبوقة مع الحد الأدنى من التكرار. من المفترض أنه لم يكن يعرف أن فانو نفسه كان يعمل في هذه المهمة في ذلك الوقت (كانت خوارزمية شانون-فانو هي الطريقة الأكثر شهرة في تلك السنوات ). نُشرت أعمال هوفمان في عام 1952 تحت عنوان طريقة لبناء رموز الحد الأدنى للتكرار في عام 1952. ومنذ ذلك الحين تم استخدام الخوارزمية على نطاق واسع.بيان صحفي لـ David Huffman UC Santa Cruz.تقوم خوارزمية هوفمان بإنشاء كود غير معاد الحد الأدنى من التكرار لمجموعة الأحرف وتكرار استخدامها. تقوم الخوارزمية بشكل متكرر باختيار حرفين أقل احتمالًا للعثور عليهما في بيانات المصدر - لنقل ، X و Y - واستبدالهما بحرف مركب يعني "X أو Y". تردد حدوث رمز مركب هو مجموع ترددات رمزي المصدر. يمكن أن تكون كلمات التشفير لكل من X و Y أي كلمات تشفير يتم تعيينها إلى الحرف المركب "X أو Y" متبوعًا بـ 0 أو 1 للتمييز بين الأحرف الأصلية. عندما يتم تقليل بيانات الإدخال إلى حرف واحد ، تتوقف الخوارزمية عن العمل ( شرح الفيديو ).فيما يلي مثال على الخوارزمية التي تعمل على مجموعة أحرف صغيرة:التكرار الأول للمعالجة:تتم إزالة الرمزين الأندر ، C و D ، من المجموعة واستبدالهما برمز مركب تردده هو مجموع الترددات C و D:الآن أندر الرموز هي B ورمز مركب بتردد 5. يتم إزالتها من المجموعة واستبدالها برمز مركب بتردد 9:وأخيرًا ، يتم دمج A ورمز مركب بتردد 9 في رمز جديد بتردد 15:تم تخفيض المجموعة بأكملها إلى حرف واحد ، اكتمال المعالجة.خلقت الخوارزمية بنية تسمى شجرة هوفمان . أحرف الإدخال هي أوراق ، وكلما زاد تواتر الحرف ، زاد ارتفاعه. بدءًا من جذر الشجرة ، يمكنك إنشاء كلمات مشفرة للأحرف بإضافة 0 أو 1 عند التحرك يسارًا أو يمينًا ، على التوالي. اتضح مثل هذا:لا توجد كلمة مشفرة بادئة لأي أخرى. كلما حدث رمز ، كلما كانت كلمة السر أقصر.يمكن أيضًا استخدام الشجرة لفك التشفير: نبدأ من الجذر وننتقل يمينًا أو يسارًا للقيمة مع 0 أو 1 أمام الحرف. على سبيل المثال ، يتم فك الخط 010100 في ABBA.لاحظ أن طول كل كلمة مشفرة يعادل عمق عقدة الشجرة المقابلة. كما سنرى في الجزء التالي ، لسنا بحاجة إلى شجرة حقيقية لتعيين كلمات مشفرة. يكفي أن تعرف طول الكلمات نفسها. وبالتالي ، ستكون نتيجة تطبيقنا لخوارزمية هوفمان هي طول كلمات الشفرة.لتخزين مجموعة الأحرف والعثور على أقل ترددات بكفاءة ، سنستخدم بنية بيانات كومة الذاكرة المؤقتة الثنائية . على وجه الخصوص ، نحن مهتمونmin-heap ، حيث يجب أن تكون القيمة الدنيا في الأعلى.
static void swap32(uint32_t *a, uint32_t *b)
{
uint32_t tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
static void minheap_down(uint32_t *heap, size_t n, size_t i)
{
size_t left, right, min;
assert(i >= 1 && i <= n && "i must be inside the heap");
while (i * 2 <= n) {
left = i * 2;
right = i * 2 + 1;
min = left;
if (right <= n && heap[right] < heap[left]) {
min = right;
}
if (heap[min] < heap[i]) {
swap32(&heap[min], &heap[i]);
i = min;
} else {
break;
}
}
}
static void minheap_heapify(uint32_t *heap, size_t n)
{
size_t i;
for (i = n / 2; i >= 1; i--) {
minheap_down(heap, n, i);
}
}
لتتبع تكرار n
الحروف ، سنستخدم مجموعة من n
العناصر. أيضًا ، في كل مرة يتم فيها إنشاء رمز مركب ، نريد "ربط" رمزي المصدر به. لذلك ، سيكون لكل رمز "عنصر اتصال".لتخزين n
كومة العنصر n
وعناصر الاتصال ، سنستخدم مجموعة من n * 2 + 1
العناصر. عندما يتم استبدال حرفين على كومة بأخرى ، سوف نستخدم العنصر الثاني لحفظ الارتباط إلى الحرف الجديد. يعتمد هذا النهج على تنفيذ إدارة غيغابايت من Witten و Moffat و Bell.في كل عقدة في الكومة ، سنستخدم 16 بت الأكثر أهمية لتخزين تردد الرمز ، و 16 بت الأقل أهمية لتخزين فهرس عنصر اتصال الرمز. نظرًا لاستخدام البتات العالية ، سيتم تحديد فرق التردد من خلال مقارنة 32 بت بين عنصري كومة الذاكرة المؤقتة.بسبب هذا التمثيل ، نحتاج إلى التأكد من أن تردد الأحرف يتناسب دائمًا مع 16 بت. بعد الانتهاء من الخوارزمية ، سيكون للرمز المركب النهائي تردد جميع الرموز المدمجة ، أي أنه يجب وضع هذا المجموع في 16 بت. سيتحقق تطبيق Deflate من هذا من خلال معالجة ما يصل إلى 64.535 حرفًا في وقت واحد.ستستقبل الرموز ذات التردد الصفري كلمات كود بطول صفري ولن تشارك في تجميع الترميز.إذا وصلت كلمة الشفرة إلى أقصى عمق محدد ، فسنقوم "بتخفيف" توزيع التردد من خلال فرض حد للتردد وإعادة المحاولة (نعم ، بمساعدة goto
). هناك طرق أكثر تعقيدًا للقيام بتشفير Huffman المحدود بعمق ، ولكن هذه الطريقة بسيطة وفعالة.#define MAX_HUFFMAN_SYMBOLS 288
static void compute_huffman_lengths(const uint16_t *freqs, size_t n,
uint8_t max_len, uint8_t *lengths)
{
uint32_t nodes[MAX_HUFFMAN_SYMBOLS * 2 + 1], p, q;
uint16_t freq;
size_t i, h, l;
uint16_t freq_cap = UINT16_MAX;
#ifndef NDEBUG
uint32_t freq_sum = 0;
for (i = 0; i < n; i++) {
freq_sum += freqs[i];
}
assert(freq_sum <= UINT16_MAX && "Frequency sum too large!");
#endif
assert(n <= MAX_HUFFMAN_SYMBOLS);
assert((1U << max_len) >= n && "max_len must be large enough");
try_again:
h = 0;
for (i = 0; i < n; i++) {
freq = freqs[i];
if (freq == 0) {
continue;
}
if (freq > freq_cap) {
freq = freq_cap;
}
h++;
nodes[h] = ((uint32_t)freq << 16) | (uint32_t)(n + h);
}
minheap_heapify(nodes, h);
if (h < 2) {
for (i = 0; i < n; i++) {
lengths[i] = (freqs[i] == 0) ? 0 : 1;
}
return;
}
while (h > 1) {
p = nodes[1];
nodes[1] = nodes[h--];
minheap_down(nodes, h, 1);
q = nodes[1];
nodes[1] = ((p & 0xffff0000) + (q & 0xffff0000))
| (uint32_t)(h + 1);
nodes[p & 0xffff] = nodes[q & 0xffff] = (uint32_t)(h + 1);
minheap_down(nodes, h, 1);
}
h = 0;
for (i = 0; i < n; i++) {
if (freqs[i] == 0) {
lengths[i] = 0;
continue;
}
h++;
p = nodes[n + h];
l = 1;
while (p != 2) {
l++;
p = nodes[p];
}
if (l > max_len) {
assert(freq_cap != 1 && "Cannot lower freq_cap!");
freq_cap /= 2;
goto try_again;
}
assert(l <= UINT8_MAX);
lengths[i] = (uint8_t)l;
}
}
البديل الأنيق لخيار كومة الذاكرة الثنائية هو تخزين الأحرف في طابور. يحتوي الأول على أحرف المصدر ، مرتبة حسب التردد. عندما يتم إنشاء رمز مركب ، يتم إضافته بشكل ثانوي. وبالتالي ، سيكون الرمز ذو التردد الأقل دائمًا في الموضع الأول لأحد قوائم الانتظار. تم وصف هذا النهج من قبل جان فان ليوين في "بناء أشجار هوفمان" (1976).هوفمان الترميز هو الأمثل لرموز غير البادئة، ولكن في حالات أخرى هناك طرق أكثر كفاءة: الحسابية الترميز و نظم عدد غير المتماثلة .رموز هوفمان القانونية
في المثال أعلاه ، قمنا ببناء شجرة هوفمان:إذا انتقلنا من الجذر واستخدمنا 0 للفرع الأيسر و 1 لليمين ، فإننا نحصل على الرموز التالية:يبدو قرار استخدام 0 للفرع الأيسر و 1 للفرع الأيمن تعسفياً. إذا فعلنا العكس نحصل على:يمكننا تمييز فرعين بشكل تعسفي منشأ من عقدة بصفر وفرع (الشيء الرئيسي هو أن التسميات مختلفة) ، وما زلنا نحصل على الرمز المكافئ:على الرغم من أن خوارزمية هوفمان توفر أطوال كلمات الكود المطلوبة للكود غير المعاد إصلاحه مع الحد الأدنى من التكرار ، فهناك العديد من الطرق لتعيين كلمات الكود الفردية.بالنظر إلى طول كلمة الشفرة المحسوبة بواسطة خوارزمية هوفمان ، فإن رمز هوفمان المعيّن يعين كلمات الشفرة إلى الأحرف بطريقة معينة. هذا مفيد لأنه يسمح لك بتخزين ونقل أطوال كلمات التشفير باستخدام البيانات المضغوطة: سيكون مفكك التشفير قادرًا على استعادة كلمات التشفير بناءً على أطوالها. بالطبع ، يمكنك تخزين ترددات الرمز ونقلها وتشغيل خوارزمية هوفمان في وحدة فك الترميز ، ولكن هذا سيتطلب المزيد من العمل والمزيد من التخزين من وحدة فك الترميز. خاصية أخرى مهمة للغاية هي أن بنية الرموز الأساسية تستخدم فك تشفير فعال.تكمن الفكرة في تعيين كلمات مشفرة للأحرف بالتسلسل ، واحدة تلو الأخرى. كلمة الكود الأولى هي 0. والكلمة التالية ستكون كلمة بطول الكلمة السابقة + 1. تتكون الكلمة الأولى بطول N من الكلمة الأخيرة بطول N-1 ، وإضافة كلمة واحدة (للحصول على كلمة كود جديدة) وتحويل خطوة واحدة إلى اليسار (لزيادة الطول).في مصطلحات شجرة هوفمان ، يتم تعيين كلمات الشفرة بشكل تسلسلي للأوراق بالترتيب من اليسار إلى اليمين ، مستوى واحد في كل مرة ، والانتقال إلى اليسار عند الانتقال إلى المستوى التالي.في مثال ABCD ، قامت خوارزمية هوفمان بتعيين كلمات كود بأطوال 1 و 2 و 3 و 3. الكلمة الأولى هي 0. وهذه أيضًا هي آخر كلمة من الطول 1. بالنسبة للطول 2 ، نأخذ 0 ونضيف 1 للحصول على الرمز التالي ، والذي سيصبح بادئة لرموز ثنائية ، انتقل إلى اليسار واحصل على 10. هذه هي الكلمة الأخيرة من الطول 2. للحصول على الطول 3 ، نضيف 1 ونحول: 110. للحصول على الكلمة التالية من الطول 3 نضيف 1: 111.يظهر تنفيذ منشئ رمز الكنسي أدناه. لاحظ أن خوارزمية الانكماش تتوقع أن يتم إنشاء كلمات مشفرة على أساس مبدأ LSB-first (أولاً ، البت الأقل أهمية). أي أنه يجب تخزين البتة الأولى من الكلمة الشفرية في البتة الأقل دلالة. هذا يعني أننا بحاجة إلى تغيير ترتيب البت ، على سبيل المثال ، باستخدام جدول البحث.#define MAX_HUFFMAN_BITS 15
static void compute_canonical_code(uint16_t *codewords, const uint8_t *lengths,
size_t n)
{
size_t i;
uint16_t count[MAX_HUFFMAN_BITS + 1] = {0};
uint16_t code[MAX_HUFFMAN_BITS + 1];
int l;
for (i = 0; i < n; i++) {
count[lengths[i]]++;
}
count[0] = 0;
code[0] = 0;
for (l = 1; l <= MAX_HUFFMAN_BITS; l++) {
code[l] = (uint16_t)((code[l - 1] + count[l - 1]) << 1);
}
for (i = 0; i < n; i++) {
l = lengths[i];
if (l == 0) {
continue;
}
codewords[i] = reverse16(code[l]++, l);
}
}
static inline uint16_t reverse16(uint16_t x, int n)
{
uint16_t lo, hi;
uint16_t reversed;
assert(n > 0);
assert(n <= 16);
lo = x & 0xff;
hi = x >> 8;
reversed = (uint16_t)((reverse8_tbl[lo] << 8) | reverse8_tbl[hi]);
return reversed >> (16 - n);
}
الآن ضع كل شيء معًا واكتب كود تهيئة برنامج التشفير:typedef struct huffman_encoder_t huffman_encoder_t;
struct huffman_encoder_t {
uint16_t codewords[MAX_HUFFMAN_SYMBOLS];
uint8_t lengths[MAX_HUFFMAN_SYMBOLS];
};
void huffman_encoder_init(huffman_encoder_t *e, const uint16_t *freqs, size_t n,
uint8_t max_codeword_len)
{
assert(n <= MAX_HUFFMAN_SYMBOLS);
assert(max_codeword_len <= MAX_HUFFMAN_BITS);
compute_huffman_lengths(freqs, n, max_codeword_len, e->lengths);
compute_canonical_code(e->codewords, e->lengths, n);
}
نقوم أيضًا بعمل وظيفة لتهيئة المشفر باستخدام أطوال الشفرة المحسوبة بالفعل:
void huffman_encoder_init2(huffman_encoder_t *e, const uint8_t *lengths,
size_t n)
{
size_t i;
for (i = 0; i < n; i++) {
e->lengths[i] = lengths[i];
}
compute_canonical_code(e->codewords, e->lengths, n);
}
كفاءة فك هوفمان
أسهل طريقة لفك شفرة Huffman هي اجتياز الشجرة بدءًا من الجذر ، وقراءة جزء واحد من المدخلات في كل مرة وتحديد الفرع الذي يجب اتخاذه بعد ذلك ، إلى اليسار أو اليمين. عند الوصول إلى عقدة ورقة ، يكون حرفًا مشفرًا.غالبًا ما يتم تدريس هذه الطريقة في الجامعات والكتب. إنه بسيط وأنيق ، ولكن المعالجة الواحدة تلو الأخرى بطيئة جدًا. إنه أسرع بكثير لفك التشفير باستخدام جدول البحث. في المثال أعلاه ، حيث يبلغ الحد الأقصى لطول كلمة السر ثلاثة بتات ، يمكنك استخدام الجدول التالي:على الرغم من وجود أربعة أحرف فقط ، نحتاج إلى جدول يحتوي على ثمانية إدخالات لتغطية جميع مجموعات الثلاثة بت الممكنة. تحتوي الرموز التي تحتوي على كلمات مشفرة أقصر من ثلاث بتات على عدة إدخالات في الجدول. على سبيل المثال ، تم "تكملة" الكلمة 10 بالرقم 10 0 و 10 1 لتغطية جميع مجموعات الثلاثة بتات التي تبدأ بـ 10.لفك الشفرة بهذه الطريقة ، تحتاج إلى الفهرسة في الجدول باستخدام وحدات بت الإدخال الثلاثة التالية والعثور على الفور على الحرف المقابل وطول كلمة الكود الخاصة به. الطول مهم ، لأنه على الرغم من النظر إلى البتات الثلاثة التالية ، نحتاج إلى الحصول على نفس عدد بتات الإدخال مثل طول كلمة التشفير.تعمل الطريقة المستندة إلى جدول البحث بسرعة كبيرة ، ولكن لها عيبًا: يتضاعف حجم الجدول مع كل بت إضافي في طول كلمة التشفير. أي أن بناء الجدول يتباطأ بشكل كبير ، وإذا توقف عن ملاءمته في ذاكرة التخزين المؤقت للمعالج ، فستبدأ الطريقة في العمل ببطء.وبسبب هذا ، يتم استخدام جدول البحث عادةً فقط للكلمات البرمجية التي لا يزيد طولها عن طول معين. وللكلمات الأطول تتخذ نهجًا مختلفًا. مثلما يقوم ترميز Huffman بتعيين كلمات مشفرة أقصر لشخصيات أكثر تكرارًا ، فإن استخدام جدول بحث لكلمات مشفرة قصيرة هو في كثير من الحالات تحسين ممتاز.في زليبيتم استخدام عدة مستويات من جداول البحث. إذا كانت كلمة الكود طويلة جدًا بالنسبة للجدول الأول ، فسيذهب البحث إلى الجدول الثانوي لفهرسة البتات المتبقية.ولكن هناك طريقة أخرى أنيقة للغاية ، تستند إلى خصائص رموز هوفمان القانونية. وقد تم وصفه في " حول تنفيذ الحد الأدنى من رموز بادئة التكرار (موفات وتوربين ، 1997) ، كما تم شرحه في ورقة تشارلز بلوم The Lost Huffman Paper .لنأخذ كلمات الشفرة من النسخة المتعارف عليها: 0 ، 10 ، 110 ، 111. سنتتبع كلمات الشفرة الأولى لكل طول ، بالإضافة إلى عدد كل كلمة كود في التسلسل العام - "فهرس الرموز".نظرًا لأن كلمات التشفير يتم تعيينها بالتسلسل ، إذا عرفنا عدد البتات ، فيمكننا العثور في الجدول أعلاه على الحرف الذي تمثله هذه البتات. على سبيل المثال ، بالنسبة للثلاثة 111 بت ، نرى أن هذا يمثل إزاحة بواسطة واحد من أول كلمة مشفرة بهذا الطول (110). مؤشر الحرف الأول من هذا الطول هو 3 ، وتعطينا إزاحة واحد فهرس 4. يقارن جدول آخر فهرس الحرف بالحرف:sym_idx = d->first_symbol[len] + (bits - d->first_code[len]);
sym = d->syms[sym_idx];
القليل من التحسين: بدلاً من تخزين فهرس الحرف الأول وكلمة الكود الأولى بشكل منفصل ، يمكننا تخزين الفهرس الأول مطروحًا منه أول كلمة مشفرة في الجدول:sym_idx = d->offset_first_sym_idx[len] + bits;
sym = d->syms[sym_idx];
لفهم عدد البتات التي يجب تقديرها ، نستخدم مرة أخرى خاصية تسلسل الكود. في مثالنا ، تكون جميع كلمات التشفير الصالحة ذات البتة الواحدة أقل من 1 ، بتين - أقل من 11 ، ثلاث بتات - أقل من 1000 (في الواقع ، صحيح لجميع قيم الثلاثة بت). بمعنى آخر ، يجب أن تكون كلمة شفرة N-bit الصالحة أقل بكثير من كلمة شفرة N-bit الأولى بالإضافة إلى عدد كلمات شفرة N-bit. علاوة على ذلك ، يمكننا تحويل هذه الحدود إلى اليسار بحيث تكون كلها بعرض ثلاثة بت. دعنا نسميها بتات تقييدية لكل من أطوال كلمات الترميز:تم تجاوز محدد الطول 3 إلى 4 بت ، ولكن هذا يعني فقط أن أي كلمة من ثلاث بتات ستفعل.يمكننا البحث بين بيانات الإدخال المكونة من ثلاثة بتات والمقارنة مع البتات المقيدة لفهم مدة كلمة المرور الخاصة بنا. بعد الانتهاء ، نحول بتات الإدخال ، فقط لحساب العدد الصحيح لها ، ثم نعثر على فهرس الأحرف:for (len = 1; len <= 3; len++) {
if (bits < d->sentinel_bits[len]) {
bits >>= 3 - len;
sym_idx = d->offset_first_sym_idx[len] + bits;
}
}
يكون تعقيد الوقت للعملية خطيًا فيما يتعلق بعدد البتات في كلمات الشفرة ، ولكن يتم إنفاق المكان بكفاءة ، ولا يلزم سوى التحميل والمقارنة في كل خطوة ، وبما أن كلمات الشفرات الأقصر هي الأكثر شيوعًا ، تسمح الطريقة بتحسين الضغط في العديد من المواقف.رمز وحدة فك الترميز الكاملة:#define HUFFMAN_LOOKUP_TABLE_BITS 8
typedef struct huffman_decoder_t huffman_decoder_t;
struct huffman_decoder_t {
struct {
uint16_t sym : 9;
uint16_t len : 7;
} table[1U << HUFFMAN_LOOKUP_TABLE_BITS];
uint16_t sentinel_bits[MAX_HUFFMAN_BITS + 1];
uint16_t offset_first_sym_idx[MAX_HUFFMAN_BITS + 1];
uint16_t syms[MAX_HUFFMAN_SYMBOLS];
#ifndef NDEBUG
size_t num_syms;
#endif
};
static inline uint64_t lsb(uint64_t x, int n)
{
assert(n >= 0 && n <= 63);
return x & (((uint64_t)1 << n) - 1);
}
static inline int huffman_decode(const huffman_decoder_t *d, uint16_t bits,
size_t *num_used_bits)
{
uint64_t lookup_bits;
size_t l;
size_t sym_idx;
lookup_bits = lsb(bits, HUFFMAN_LOOKUP_TABLE_BITS);
assert(lookup_bits < sizeof(d->table) / sizeof(d->table[0]));
if (d->table[lookup_bits].len != 0) {
assert(d->table[lookup_bits].len <= HUFFMAN_LOOKUP_TABLE_BITS);
assert(d->table[lookup_bits].sym < d->num_syms);
*num_used_bits = d->table[lookup_bits].len;
return d->table[lookup_bits].sym;
}
bits = reverse16(bits, MAX_HUFFMAN_BITS);
for (l = HUFFMAN_LOOKUP_TABLE_BITS + 1; l <= MAX_HUFFMAN_BITS; l++) {
if (bits < d->sentinel_bits[l]) {
bits >>= MAX_HUFFMAN_BITS - l;
sym_idx = (uint16_t)(d->offset_first_sym_idx[l] + bits);
assert(sym_idx < d->num_syms);
*num_used_bits = l;
return d->syms[sym_idx];
}
}
*num_used_bits = 0;
return -1;
}
لتهيئة مفكك التشفير ، سنحسب الشفرات الأساسية مسبقًا ، مثل huffman_encoder_init ، ونملأ جداول مختلفة:
bool huffman_decoder_init(huffman_decoder_t *d, const uint8_t *lengths,
size_t n)
{
size_t i;
uint16_t count[MAX_HUFFMAN_BITS + 1] = {0};
uint16_t code[MAX_HUFFMAN_BITS + 1];
uint32_t s;
uint16_t sym_idx[MAX_HUFFMAN_BITS + 1];
int l;
#ifndef NDEBUG
assert(n <= MAX_HUFFMAN_SYMBOLS);
d->num_syms = n;
#endif
for (i = 0; i < sizeof(d->table) / sizeof(d->table[0]); i++) {
d->table[i].len = 0;
}
for (i = 0; i < n; i++) {
assert(lengths[i] <= MAX_HUFFMAN_BITS);
count[lengths[i]]++;
}
count[0] = 0;
code[0] = 0;
sym_idx[0] = 0;
for (l = 1; l <= MAX_HUFFMAN_BITS; l++) {
code[l] = (uint16_t)((code[l - 1] + count[l - 1]) << 1);
if (count[l] != 0 && code[l] + count[l] - 1 > (1U << l) - 1) {
return false;
}
s = (uint32_t)((code[l] + count[l]) << (MAX_HUFFMAN_BITS - l));
d->sentinel_bits[l] = (uint16_t)s;
assert(d->sentinel_bits[l] == s && "No overflow.");
sym_idx[l] = sym_idx[l - 1] + count[l - 1];
d->offset_first_sym_idx[l] = sym_idx[l] - code[l];
}
for (i = 0; i < n; i++) {
l = lengths[i];
if (l == 0) {
continue;
}
d->syms[sym_idx[l]] = (uint16_t)i;
sym_idx[l]++;
if (l <= HUFFMAN_LOOKUP_TABLE_BITS) {
table_insert(d, i, l, code[l]);
code[l]++;
}
}
return true;
}
static void table_insert(huffman_decoder_t *d, size_t sym, int len,
uint16_t codeword)
{
int pad_len;
uint16_t padding, index;
assert(len <= HUFFMAN_LOOKUP_TABLE_BITS);
codeword = reverse16(codeword, len);
pad_len = HUFFMAN_LOOKUP_TABLE_BITS - len;
for (padding = 0; padding < (1U << pad_len); padding++) {
index = (uint16_t)(codeword | (padding << len));
d->table[index].sym = (uint16_t)sym;
d->table[index].len = (uint16_t)len;
assert(d->table[index].sym == sym && "Fits in bitfield.");
assert(d->table[index].len == len && "Fits in bitfield.");
}
}
فرغ
خوارزمية الانكماش ، المقدمة في PKZip 2.04c في عام 1993 ، هي طريقة ضغط قياسية في ملفات Zip الحديثة. يتم استخدامه أيضًا في gzip و PNG والعديد من التنسيقات الأخرى. يستخدم مزيجًا من ضغط LZ77 وترميز هوفمان ، والذي سنناقشه وننفذه في هذا القسم.قبل انكماش ، استخدم PKZip طرق الضغط Shrink و Reduce و Implode. اليوم أصبحت نادرة ، على الرغم من أن Deflate كانت لا تزال تستخدم لبعض الوقت ، لأنها تستهلك ذاكرة أقل. لكننا لن ننظر فيها.تدفقات بت
يقوم Deflate بتخزين كلمات هودمان الشفرية في تدفق بتات وفقًا لمبدأ LSB-first. وهذا يعني أنه يتم تخزين البتة الأولى من الدفق في البتة الأقل دلالة من البايت الأول.ضع في اعتبارك تدفق البت (اقرأ من اليسار إلى اليمين) 1-0-0-1-1. عندما يتم تخزينها وفقًا لمبدأ LSB الأول ، تصبح قيمة البايت 0b00011001 (ثنائي) أو 0x19 (سداسي عشري). قد يبدو أن الدفق يمثل ببساطة إلى الوراء (بمعنى ما ،) ، ولكن الميزة هي أنه من الأسهل بالنسبة لنا الحصول على أول بت N من كلمة الكمبيوتر: نحن ببساطة نخفي البتات الأقل أهمية.تؤخذ هذه الإجراءات من bitstream.h :
typedef struct istream_t istream_t;
struct istream_t {
const uint8_t *src;
const uint8_t *end;
size_t bitpos;
size_t bitpos_end;
};
static inline void istream_init(istream_t *is, const uint8_t *src, size_t n)
{
is->src = src;
is->end = src + n;
is->bitpos = 0;
is->bitpos_end = n * 8;
}
يحتاج مفكك تشفير Huffman إلى النظر في البتات التالية في الدفق (بتات كافية لأطول كلمة مشفرة ممكنة) ، ثم متابعة الدفق بعدد البتات التي يستخدمها الرمز الذي تم فك ترميزه:#define ISTREAM_MIN_BITS (64 - 7)
static inline uint64_t istream_bits(const istream_t *is)
{
const uint8_t *next;
uint64_t bits;
int i;
next = is->src + (is->bitpos / 8);
assert(next <= is->end && "Cannot read past end of stream.");
if (is->end - next >= 8) {
bits = read64le(next);
} else {
bits = 0;
for (i = 0; i < is->end - next; i++) {
bits |= (uint64_t)next[i] << (i * 8);
}
}
return bits >> (is->bitpos % 8);
}
static inline bool istream_advance(istream_t *is, size_t n) {
if (is->bitpos + n > is->bitpos_end) {
return false;
}
is->bitpos += n;
return true;
}
خلاصة القول هي أنه على الأجهزة ذات 64 بت ، istream_bits
يمكنك عادةً تنفيذها كإرشادات تمهيد واحد وبعض العمليات الحسابية ، نظرًا لأن عناصر الهيكل istream_t
موجودة في السجلات. يتم تنفيذ read64le في bits.h (يقوم المترجمون الحديثون بتحويله إلى تنزيل 64 بت واحد باستخدام مبدأ endian الصغير):
static inline uint64_t read64le(const uint8_t *p)
{
return ((uint64_t)p[0] << 0) |
((uint64_t)p[1] << 8) |
((uint64_t)p[2] << 16) |
((uint64_t)p[3] << 24) |
((uint64_t)p[4] << 32) |
((uint64_t)p[5] << 40) |
((uint64_t)p[6] << 48) |
((uint64_t)p[7] << 56);
}
نحتاج أيضًا إلى وظيفة لمتابعة تدفق البتات حتى حدود البايت التالي:
static inline size_t round_up(size_t x, size_t m)
{
assert((m & (m - 1)) == 0 && "m must be a power of two");
return (x + m - 1) & (size_t)(-m);
}
static inline const uint8_t *istream_byte_align(istream_t *is)
{
const uint8_t *byte;
assert(is->bitpos <= is->bitpos_end && "Not past end of stream.");
is->bitpos = round_up(is->bitpos, 8);
byte = is->src + is->bitpos / 8;
assert(byte <= is->end);
return byte;
}
بالنسبة لتدفق البتات الصادرة ، نكتب البتات باستخدام عملية قراءة - تعديل - كتابة. في الحالة السريعة ، يمكنك الكتابة قليلاً باستخدام قراءة 64 بت ، ونوع من عمليات البت ، وكتابة 64 بت.
typedef struct ostream_t ostream_t;
struct ostream_t {
uint8_t *dst;
uint8_t *end;
size_t bitpos;
size_t bitpos_end;
};
static inline void ostream_init(ostream_t *os, uint8_t *dst, size_t n)
{
os->dst = dst;
os->end = dst + n;
os->bitpos = 0;
os->bitpos_end = n * 8;
}
static inline size_t ostream_bit_pos(const ostream_t *os)
{
return os->bitpos;
}
static inline size_t ostream_bytes_written(ostream_t *os)
{
return round_up(os->bitpos, 8) / 8;
}
static inline bool ostream_write(ostream_t *os, uint64_t bits, size_t n)
{
uint8_t *p;
uint64_t x;
int shift, i;
assert(n <= 57);
assert(bits <= ((uint64_t)1 << n) - 1 && "Must fit in n bits.");
if (os->bitpos_end - os->bitpos < n) {
return false;
}
p = &os->dst[os->bitpos / 8];
shift = os->bitpos % 8;
if (os->end - p >= 8) {
x = read64le(p);
x = lsb(x, shift);
x |= bits << shift;
write64le(p, x);
} else {
x = 0;
for (i = 0; i < os->end - p; i++) {
x |= (uint64_t)p[i] << (i * 8);
}
x = lsb(x, shift);
x |= bits << shift;
for (i = 0; i < os->end - p; i++) {
p[i] = (uint8_t)(x >> (i * 8));
}
}
os->bitpos += n;
return true;
}
static inline void write64le(uint8_t *dst, uint64_t x)
{
dst[0] = (uint8_t)(x >> 0);
dst[1] = (uint8_t)(x >> 8);
dst[2] = (uint8_t)(x >> 16);
dst[3] = (uint8_t)(x >> 24);
dst[4] = (uint8_t)(x >> 32);
dst[5] = (uint8_t)(x >> 40);
dst[6] = (uint8_t)(x >> 48);
dst[7] = (uint8_t)(x >> 56);
}
نحتاج أيضًا إلى كتابة وحدات البايت بكفاءة إلى الدفق. بالطبع ، يمكنك تنفيذ تسجيلات 8 بت بشكل متكرر ، ولكن سيكون استخدامها أسرع memcpy
:
static inline bool ostream_write_bytes_aligned(ostream_t *os,
const uint8_t *src,
size_t n)
{
if (os->bitpos_end - round_up(os->bitpos, 8) < n * 8) {
return false;
}
os->bitpos = round_up(os->bitpos, 8);
memcpy(&os->dst[os->bitpos / 8], src, n);
os->bitpos += n * 8;
return true;
}
تفريغ (التضخم)
نظرًا لأن خوارزمية الضغط تسمى الانكماش - النفخ ، واستخراج الهواء من شيء ما - تسمى عملية التفريغ أحيانًا بالتضخم . إذا درست هذه العملية لأول مرة ، فسوف نفهم كيف يعمل التنسيق. تستطيع أن ترى في التعليمات البرمجية في الجزء الأول من deflate.h و deflate.c ، bits.h ، tables.h و tables.c (تم إنشاؤها باستخدام generate_tables.c ).يتم تخزين البيانات المضغوطة باستخدام Deflate كسلسلة من الكتل.. تبدأ كل فدرة برأس 3 بت ، حيث يتم تعيين البت الأول (الأقل أهمية) إذا كانت هذه هي الكتلة النهائية للسلسلة ، وتشير البتتان الأخريان إلى نوعها.هناك ثلاثة أنواع من الكتل: غير مضغوط (0) ، مضغوط باستخدام رموز Huffman الثابتة (1) ، ومضغوط باستخدام رموز Huffman "ديناميكية" (2).ينفذ هذا الكود التفريغ باستخدام وظائف مساعدة لأنواع مختلفة من الكتل ، والتي سنقوم بتنفيذها لاحقًا:typedef enum {
HWINF_OK,
HWINF_FULL,
HWINF_ERR
} inf_stat_t;
inf_stat_t hwinflate(const uint8_t *src, size_t src_len, size_t *src_used,
uint8_t *dst, size_t dst_cap, size_t *dst_used)
{
istream_t is;
size_t dst_pos;
uint64_t bits;
bool bfinal;
inf_stat_t s;
istream_init(&is, src, src_len);
dst_pos = 0;
do {
bits = istream_bits(&is);
if (!istream_advance(&is, 3)) {
return HWINF_ERR;
}
bfinal = bits & 1;
bits >>= 1;
switch (lsb(bits, 2)) {
case 0:
s = inf_noncomp_block(&is, dst, dst_cap, &dst_pos);
break;
case 1:
s = inf_fixed_block(&is, dst, dst_cap, &dst_pos);
break;
case 2:
s = inf_dyn_block(&is, dst, dst_cap, &dst_pos);
break;
default:
return HWINF_ERR;
}
if (s != HWINF_OK) {
return s;
}
} while (!bfinal);
*src_used = (size_t)(istream_byte_align(&is) - src);
assert(dst_pos <= dst_cap);
*dst_used = dst_pos;
return HWINF_OK;
}
كتل مفرغة غير مضغوطة
هذه هي كتل "المخزنة" ، أبسط نوع. ويبدأ بالحدود التالية المكونة من 8 بتة من تدفق البتات بكلمة من 16 بت (len) تدل على طول الكتلة. خلفها كلمة أخرى من 16 بت (nlen) ، والتي تكمل (يتم عكس ترتيب البتات) من الكلمات len. من المفترض أن nlen يعمل كمجموع تدقيق بسيط: إذا كان الملف تالفًا ، فمن المحتمل ألا تكون القيم مكملة وسيتمكن البرنامج من اكتشاف الخطأ.بعد len و nlen بيانات غير مضغوطة. نظرًا لأن طول الكتلة هو قيمة 16 بت ، فإن حجم البيانات يقتصر على 65535 بايت.static inf_stat_t inf_noncomp_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
const uint8_t *p;
uint16_t len, nlen;
p = istream_byte_align(is);
if (!istream_advance(is, 32)) {
return HWINF_ERR;
}
len = read16le(p);
nlen = read16le(p + 2);
p += 4;
if (nlen != (uint16_t)~len) {
return HWINF_ERR;
}
if (!istream_advance(is, len * 8)) {
return HWINF_ERR;
}
if (dst_cap - *dst_pos < len) {
return HWINF_FULL;
}
memcpy(&dst[*dst_pos], p, len);
*dst_pos += len;
return HWINF_OK;
}
فرغ الكتل باستخدام رموز هوفمان الثابتة
تستخدم كتل الانكماش المضغوطة كود Huffman لتمثيل سلسلة من LZ77. يتم كسر الروابط الخلفية باستخدام علامات نهاية الكتلة. بالنسبة للحروف وأطوال الروابط الخلفية والعلامات ، يتم استخدام رمز litlen Huffman . وبالنسبة لمسافات الوصلات الخلفية ، يتم استخدام كود dist .ترميز Litlen القيم في النطاق 0-285. تُستخدم القيم 0-255 للبايتات الحرفية ، و 256 هي علامة نهاية الكتلة ، و 257-285 تستخدم لأطوال الوصلات الخلفية.يبلغ طول الروابط الخلفية 3-258 بايت. تحدد قيمة Litlen الطول الأساسي الذي يضاف إليه صفر بتات إضافية أو أكثر من الدفق للحصول على الطول الكامل وفقًا للجدول أدناه. على سبيل المثال ، تعني قيمة litlen 269 طولًا أساسيًا يبلغ 19 وقطعتين إضافيتين. إضافة قطعتين من التيار تعطي الطول النهائي من 19 إلى 22.يرجى ملاحظة أن قيمة litlen 284 بالإضافة إلى 5 بتات إضافية يمكن أن تمثل أطوالًا من 227 إلى 258 ، ومع ذلك ، تنص المواصفات على أنه يجب تمثيل الطول 258 - الحد الأقصى لطول الوصلة الخلفية - باستخدام قيمة litlen منفصلة. من المفترض أن يؤدي ذلك إلى تقليل الترميز في المواقف التي غالبًا ما تتم فيها مواجهة الحد الأقصى للطول.يستخدم برنامج فك الضغط الجدول للحصول على الطول الأساسي والبتات الإضافية من قيمة litlen (ناقص 257):
struct litlen_tbl_t {
uint16_t base_len : 9;
uint16_t ebits : 7;
};
const struct litlen_tbl_t litlen_tbl[29] = {
{ 3, 0 },
{ 4, 0 },
...
{ 227, 5 },
{ 258, 0 }
};
يعد رمز Litlen الثابت لـ Huffman أمرًا أساسيًا ويستخدم أطوال كلمات الشفرة التالية (286-287 ليست قيمًا صالحة لـ litlen ، ولكنها متورطة في إنشاء التعليمات البرمجية):يقوم برنامج فك الضغط بتخزين هذه الأطوال في جدول مناسب للإرسال إلى huffman_decoder_init
:const uint8_t fixed_litlen_lengths[288] = {
8,
8,
...
8,
};
تختلف مسافات الوصلة الخلفية من 1 إلى 32،768 ، ويتم تشفيرها باستخدام مخطط مشابه لمخطط تشفير الطول. يعمل كود هوفمان على تشفير القيم من 0 إلى 29 ، وكل منها يتوافق مع طول القاعدة ، والتي تضاف إليها بتات إضافية للحصول على المسافة النهائية:يعد رمز Huffman الثابت هو أمرًا قانونيًا. جميع كلمات التشفير هي 5 بت. إنه بسيط ، يقوم برنامج فك الضغط بتخزين الرموز في جدول يمكن استخدامه مع huffman_decoder_init
(قيم dist 30-31 غير صحيحة. يشار إلى أنها متورطة في توليد رموز Huffman ، ولكن ليس لها أي تأثير في الواقع):const uint8_t fixed_dist_lengths[32] = {
5,
5,
...
5,
};
فك الضغط أو فك التغليف - قم بفك الكتلة باستخدام أكواد هوفمان الثابتة:static inf_stat_t inf_fixed_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
huffman_decoder_t litlen_dec, dist_dec;
huffman_decoder_init(&litlen_dec, fixed_litlen_lengths,
sizeof(fixed_litlen_lengths) /
sizeof(fixed_litlen_lengths[0]));
huffman_decoder_init(&dist_dec, fixed_dist_lengths,
sizeof(fixed_dist_lengths) /
sizeof(fixed_dist_lengths[0]));
return inf_block(is, dst, dst_cap, dst_pos, &litlen_dec, &dist_dec);
}
#define LITLEN_EOB 256
#define LITLEN_MAX 285
#define LITLEN_TBL_OFFSET 257
#define MIN_LEN 3
#define MAX_LEN 258
#define DISTSYM_MAX 29
#define MIN_DISTANCE 1
#define MAX_DISTANCE 32768
static inf_stat_t inf_block(istream_t *is, uint8_t *dst, size_t dst_cap,
size_t *dst_pos,
const huffman_decoder_t *litlen_dec,
const huffman_decoder_t *dist_dec)
{
uint64_t bits;
size_t used, used_tot, dist, len;
int litlen, distsym;
uint16_t ebits;
while (true) {
bits = istream_bits(is);
litlen = huffman_decode(litlen_dec, (uint16_t)bits, &used);
bits >>= used;
used_tot = used;
if (litlen < 0 || litlen > LITLEN_MAX) {
return HWINF_ERR;
} else if (litlen <= UINT8_MAX) {
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
if (*dst_pos == dst_cap) {
return HWINF_FULL;
}
lz77_output_lit(dst, (*dst_pos)++, (uint8_t)litlen);
continue;
} else if (litlen == LITLEN_EOB) {
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
return HWINF_OK;
}
assert(litlen >= LITLEN_TBL_OFFSET && litlen <= LITLEN_MAX);
len = litlen_tbl[litlen - LITLEN_TBL_OFFSET].base_len;
ebits = litlen_tbl[litlen - LITLEN_TBL_OFFSET].ebits;
if (ebits != 0) {
len += lsb(bits, ebits);
bits >>= ebits;
used_tot += ebits;
}
assert(len >= MIN_LEN && len <= MAX_LEN);
distsym = huffman_decode(dist_dec, (uint16_t)bits, &used);
bits >>= used;
used_tot += used;
if (distsym < 0 || distsym > DISTSYM_MAX) {
return HWINF_ERR;
}
dist = dist_tbl[distsym].base_dist;
ebits = dist_tbl[distsym].ebits;
if (ebits != 0) {
dist += lsb(bits, ebits);
bits >>= ebits;
used_tot += ebits;
}
assert(dist >= MIN_DISTANCE && dist <= MAX_DISTANCE);
assert(used_tot <= ISTREAM_MIN_BITS);
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
if (dist > *dst_pos) {
return HWINF_ERR;
}
if (round_up(len, 8) <= dst_cap - *dst_pos) {
output_backref64(dst, *dst_pos, dist, len);
} else if (len <= dst_cap - *dst_pos) {
lz77_output_backref(dst, *dst_pos, dist, len);
} else {
return HWINF_FULL;
}
(*dst_pos) += len;
}
}
انتبه إلى هذا التحسين: عندما لا تكون هناك مساحة كافية في المخزن المؤقت الصادر ، نصدر روابط خلفية باستخدام الوظيفة أدناه ، والتي تنسخ 64 بت في المرة الواحدة. هذا "فوضوي" بمعنى أنه غالبًا ما ينسخ بضعة بايتات إضافية (حتى المضاعف التالي من 8). لكنها تعمل بشكل أسرع lz77_output_backref
، لأنها تتطلب تكرارات دورية أقل ووصول إلى الذاكرة. في الواقع ، سيتم الآن معالجة الروابط الخلفية القصيرة في تكرار واحد ، وهو أمر جيد جدًا للتنبؤ بالفروع.
static void output_backref64(uint8_t *dst, size_t dst_pos, size_t dist,
size_t len)
{
size_t i;
uint64_t tmp;
assert(len > 0);
assert(dist <= dst_pos && "cannot reference before beginning of dst");
if (len > dist) {
lz77_output_backref(dst, dst_pos, dist, len);
return;
}
i = 0;
do {
memcpy(&tmp, &dst[dst_pos - dist + i], 8);
memcpy(&dst[dst_pos + i], &tmp, 8);
i += 8;
} while (i < len);
}
افراغ الكتل باستخدام رموز Huffman الديناميكية
تعمل كتل الانكماش باستخدام رموز Huffman الديناميكية بنفس الطريقة الموضحة أعلاه. ولكن بدلاً من الرموز المحددة مسبقًا لـ litlen و dist ، يستخدمون الرموز المخزنة في دفق الانكماش نفسه في بداية الكتلة. ربما يكون الاسم غير ناجح ، لأن رموز Huffman الديناميكية تسمى أيضًا الرموز التي تتغير أثناء الترميز - وهذا هو ترميز Huffman التكيفي . الرموز الموصوفة هنا لا علاقة لها بهذا الإجراء. إنها ديناميكية فقط بمعنى أن الكتل المختلفة يمكنها استخدام رموز مختلفة.يعتبر إنشاء الرموز الديناميكية والمشتقة الديناميكية الجزء الأكثر صعوبة في تنسيق الانكماش. ولكن بمجرد إنشاء الرموز ، يتم فك الضغط بنفس الطريقة الموضحة في الجزء السابق ، باستخدام inf_block
:static inf_stat_t inf_dyn_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
inf_stat_t s;
huffman_decoder_t litlen_dec, dist_dec;
s = init_dyn_decoders(is, &litlen_dec, &dist_dec);
if (s != HWINF_OK) {
return s;
}
return inf_block(is, dst, dst_cap, dst_pos, &litlen_dec, &dist_dec);
}
يتم تخزين رموز Litlen و dist لكتل الانكماش الديناميكية كسلسلة من أطوال كلمات التشفير. يتم ترميز الأطوال نفسها باستخدام كود هوفمان الثالث - كودلين . يتم تحديد هذا الرمز من خلال طول كلمات الكود ( codelen_lens
) المخزنة في الكتلة (هل ذكرت أنه صعب؟).في بداية الكتلة الديناميكية ، هناك 14 بتة تحدد عدد أطوال كلمات التشفير ، والتشفير ، والشفرات التي يجب قراءتها من الكتلة:#define MIN_CODELEN_LENS 4
#define MAX_CODELEN_LENS 19
#define MIN_LITLEN_LENS 257
#define MAX_LITLEN_LENS 288
#define MIN_DIST_LENS 1
#define MAX_DIST_LENS 32
#define CODELEN_MAX_LIT 15
#define CODELEN_COPY 16
#define CODELEN_COPY_MIN 3
#define CODELEN_COPY_MAX 6
#define CODELEN_ZEROS 17
#define CODELEN_ZEROS_MIN 3
#define CODELEN_ZEROS_MAX 10
#define CODELEN_ZEROS2 18
#define CODELEN_ZEROS2_MIN 11
#define CODELEN_ZEROS2_MAX 138
static const int codelen_lengths_order[MAX_CODELEN_LENS] =
{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
static inf_stat_t init_dyn_decoders(istream_t *is,
huffman_decoder_t *litlen_dec,
huffman_decoder_t *dist_dec)
{
uint64_t bits;
size_t num_litlen_lens, num_dist_lens, num_codelen_lens;
uint8_t codelen_lengths[MAX_CODELEN_LENS];
uint8_t code_lengths[MAX_LITLEN_LENS + MAX_DIST_LENS];
size_t i, n, used;
int sym;
huffman_decoder_t codelen_dec;
bits = istream_bits(is);
num_litlen_lens = lsb(bits, 5) + MIN_LITLEN_LENS;
bits >>= 5;
assert(num_litlen_lens <= MAX_LITLEN_LENS);
num_dist_lens = lsb(bits, 5) + MIN_DIST_LENS;
bits >>= 5;
assert(num_dist_lens <= MAX_DIST_LENS);
num_codelen_lens = lsb(bits, 4) + MIN_CODELEN_LENS;
bits >>= 4;
assert(num_codelen_lens <= MAX_CODELEN_LENS);
if (!istream_advance(is, 5 + 5 + 4)) {
return HWINF_ERR;
}
ثم تأتي أطوال كلمات الشفرة لكود التشفير. هذه الأطوال هي القيم الثلاثية المعتادة ، ولكنها مكتوبة بالترتيب الخاص المحدد في codelen_lengths_order
. نظرًا لأنه يلزم تحديد 19 طولًا ، سيتم قراءة الدفق فقط num_codelen_lens
؛ كل شيء آخر باطل ضمنيًا. يتم سرد الأطوال بترتيب معين بحيث من المرجح أن تسقط أطوال صفرية في نهاية القائمة ولا يتم تخزينها في الكتلة.
for (i = 0; i < num_codelen_lens; i++) {
bits = istream_bits(is);
codelen_lengths[codelen_lengths_order[i]] =
(uint8_t)lsb(bits, 3);
if (!istream_advance(is, 3)) {
return HWINF_ERR;
}
}
for (; i < MAX_CODELEN_LENS; i++) {
codelen_lengths[codelen_lengths_order[i]] = 0;
}
if (!huffman_decoder_init(&codelen_dec, codelen_lengths,
MAX_CODELEN_LENS)) {
return HWINF_ERR;
}
من خلال تعيين وحدة فك ترميز codelen ، يمكننا قراءة أطوال كلمات التشفير litlen و dist من الدفق.
i = 0;
while (i < num_litlen_lens + num_dist_lens) {
bits = istream_bits(is);
sym = huffman_decode(&codelen_dec, (uint16_t)bits, &used);
bits >>= used;
if (!istream_advance(is, used)) {
return HWINF_ERR;
}
if (sym >= 0 && sym <= CODELEN_MAX_LIT) {
code_lengths[i++] = (uint8_t)sym;
}
16 و 17 و 18 ليست أطوالًا حقيقية ، فهي مؤشرات على أن الطول السابق يحتاج إلى تكرار عدة مرات ، أو أنك بحاجة إلى تكرار الطول الصفري: else if (sym == CODELEN_COPY) {
if (i < 1) {
return HWINF_ERR;
}
n = lsb(bits, 2) + CODELEN_COPY_MIN;
if (!istream_advance(is, 2)) {
return HWINF_ERR;
}
assert(n >= CODELEN_COPY_MIN && n <= CODELEN_COPY_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i] = code_lengths[i - 1];
i++;
}
} else if (sym == CODELEN_ZEROS) {
n = lsb(bits, 3) + CODELEN_ZEROS_MIN;
if (!istream_advance(is, 3)) {
return HWINF_ERR;
}
assert(n >= CODELEN_ZEROS_MIN &&
n <= CODELEN_ZEROS_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i++] = 0;
}
} else if (sym == CODELEN_ZEROS2) {
n = lsb(bits, 7) + CODELEN_ZEROS2_MIN;
if (!istream_advance(is, 7)) {
return HWINF_ERR;
}
assert(n >= CODELEN_ZEROS2_MIN &&
n <= CODELEN_ZEROS2_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i++] = 0;
}
} else {
return HWINF_ERR;
}
}
لاحظ أن أطوال litlen و dist تتم قراءتها واحدة تلو الأخرى في المصفوفة code_lengths
. لا يمكن قراءتها بشكل منفصل ، لأنه يمكن ترحيل عمليات تشغيل طول الكود من أطوال الإنارة الأخيرة إلى أطوال الإنطلاق الأولى.بعد إعداد أطوال كلمات الترميز ، يمكننا تكوين أجهزة فك التشفير Huffman والعودة إلى مهمة فك الرموز والحروف الخلفية: if (!huffman_decoder_init(litlen_dec, &code_lengths[0],
num_litlen_lens)) {
return HWINF_ERR;
}
if (!huffman_decoder_init(dist_dec, &code_lengths[num_litlen_lens],
num_dist_lens)) {
return HWINF_ERR;
}
return HWINF_OK;
}
الضغط (الانكماش)
في الأجزاء السابقة ، أنشأنا جميع الأدوات اللازمة لضغط الانكماش: Lempel-Ziv ، ترميز Huffman ، تدفقات البتات ووصف للأنواع الثلاثة من كتل الانكماش. وفي هذا الجزء سنقوم بتجميع كل شيء للحصول على ضغط الانكماش.ضغط Lempel-Ziv يوزع البيانات المصدر في سلسلة من الروابط الخلفية والحروف. يجب تقسيم هذا التسلسل وترميزه إلى كتل انكماش ، كما هو موضح في الجزء السابق. غالبًا ما يسمى اختيار طريقة التقسيم بالحجب.. من ناحية ، تعني كل كتلة جديدة نوعًا من النفقات العامة ، يعتمد حجمها على نوع الكتلة ومحتوياتها. كتل أقل - حمل أقل. من ناحية أخرى ، فإن تكاليف إنشاء كتلة جديدة يمكن أن تؤتي ثمارها. على سبيل المثال ، إذا كانت خصائص البيانات تسمح بتشفير Huffman الأكثر كفاءة وتقليل إجمالي كمية البيانات التي يتم إنشاؤها.الحظر مهمة تحسين صعبة. بعض الضواغط (على سبيل المثال ، Zopfli ) تحاول بشكل أفضل من غيرها ، ولكن معظمها ببساطة يتبع نهجًا جشعًا: يصدرون الكتل بمجرد وصولها إلى حجم معين.أنواع مختلفة من الكتل لها قيود الحجم الخاصة بها:- لا يمكن أن تحتوي الكتل غير المضغوطة على أكثر من 65.535 بايت.
- لا تحتوي رموز Huffman الثابتة على حجم أقصى.
- بشكل عام ، لا تحتوي رموز Dynamic Huffman على الحد الأقصى للحجم ، ولكن نظرًا لأن تنفيذنا لخوارزمية Huffman يستخدم تسلسلات أحرف 16 بت ، فإننا مقيدون بـ 65535 حرفًا.
لاستخدام كتل من أي نوع بحرية ، قم بقصر حجمها على 65534 بايت:
#define MAX_BLOCK_LEN_BYTES 65534
لتتبع تدفق البتات الصادرة ومحتويات الكتلة الحالية أثناء الضغط ، سنستخدم البنية:typedef struct deflate_state_t deflate_state_t;
struct deflate_state_t {
ostream_t os;
const uint8_t *block_src;
size_t block_len;
size_t block_len_bytes;
uint16_t litlen_freqs[LITLEN_MAX + 1];
uint16_t dist_freqs[DISTSYM_MAX + 1];
struct {
uint16_t distance;
union {
uint16_t lit;
uint16_t len;
} u;
} block[MAX_BLOCK_LEN_BYTES + 1];
};
static void reset_block(deflate_state_t *s)
{
s->block_len = 0;
s->block_len_bytes = 0;
memset(s->litlen_freqs, 0, sizeof(s->litlen_freqs));
memset(s->dist_freqs, 0, sizeof(s->dist_freqs));
}
لإضافة نتائج العمل إلى الكتلة ، lz77_compress
سنستخدم وظائف رد الاتصال ، وعند الوصول إلى الحجم الأقصى ، سنكتب الكتلة إلى تدفق البت:static bool lit_callback(uint8_t lit, void *aux)
{
deflate_state_t *s = aux;
if (s->block_len_bytes + 1 > MAX_BLOCK_LEN_BYTES) {
if (!write_block(s, false)) {
return false;
}
s->block_src += s->block_len_bytes;
reset_block(s);
}
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
s->block[s->block_len ].distance = 0;
s->block[s->block_len++].u.lit = lit;
s->block_len_bytes++;
s->litlen_freqs[lit]++;
return true;
}
static bool backref_callback(size_t dist, size_t len, void *aux)
{
deflate_state_t *s = aux;
if (s->block_len_bytes + len > MAX_BLOCK_LEN_BYTES) {
if (!write_block(s, false)) {
return false;
}
s->block_src += s->block_len_bytes;
reset_block(s);
}
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
s->block[s->block_len ].distance = (uint16_t)dist;
s->block[s->block_len++].u.len = (uint16_t)len;
s->block_len_bytes += len;
assert(len >= MIN_LEN && len <= MAX_LEN);
assert(dist >= MIN_DISTANCE && dist <= MAX_DISTANCE);
s->litlen_freqs[len2litlen[len]]++;
s->dist_freqs[distance2dist[dist]]++;
return true;
}
الشيء الأكثر إثارة للاهتمام هو تسجيل الكتل. إذا لم يتم ضغط الكتلة ، فكل شيء بسيط:static bool write_uncomp_block(deflate_state_t *s, bool final)
{
uint8_t len_nlen[4];
if (!ostream_write(&s->os, (0x0 << 1) | final, 3)) {
return false;
}
len_nlen[0] = (uint8_t)(s->block_len_bytes >> 0);
len_nlen[1] = (uint8_t)(s->block_len_bytes >> 8);
len_nlen[2] = ~len_nlen[0];
len_nlen[3] = ~len_nlen[1];
if (!ostream_write_bytes_aligned(&s->os, len_nlen, sizeof(len_nlen))) {
return false;
}
if (!ostream_write_bytes_aligned(&s->os, s->block_src,
s->block_len_bytes)) {
return false;
}
return true;
}
لكتابة كتلة Huffman ثابتة ، ننشئ أولاً رموزًا أساسية تستند إلى أطوال كلمات مشفرة ثابتة لرموز litlen و dist. ثم نكرر الكتلة ، ونكتب الأحرف التي تستخدم هذه الرموز:static bool write_static_block(deflate_state_t *s, bool final)
{
huffman_encoder_t litlen_enc, dist_enc;
if (!ostream_write(&s->os, (0x1 << 1) | final, 3)) {
return false;
}
huffman_encoder_init2(&litlen_enc, fixed_litlen_lengths,
sizeof(fixed_litlen_lengths) /
sizeof(fixed_litlen_lengths[0]));
huffman_encoder_init2(&dist_enc, fixed_dist_lengths,
sizeof(fixed_dist_lengths) /
sizeof(fixed_dist_lengths[0]));
return write_huffman_block(s, &litlen_enc, &dist_enc);
}
static bool write_huffman_block(deflate_state_t *s,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t i, nbits;
uint64_t distance, dist, len, litlen, bits, ebits;
for (i = 0; i < s->block_len; i++) {
if (s->block[i].distance == 0) {
litlen = s->block[i].u.lit;
assert(litlen <= LITLEN_EOB);
if (!ostream_write(&s->os,
litlen_enc->codewords[litlen],
litlen_enc->lengths[litlen])) {
return false;
}
continue;
}
len = s->block[i].u.len;
litlen = len2litlen[len];
bits = litlen_enc->codewords[litlen];
nbits = litlen_enc->lengths[litlen];
ebits = len - litlen_tbl[litlen - LITLEN_TBL_OFFSET].base_len;
bits |= ebits << nbits;
nbits += litlen_tbl[litlen - LITLEN_TBL_OFFSET].ebits;
distance = s->block[i].distance;
dist = distance2dist[distance];
bits |= (uint64_t)dist_enc->codewords[dist] << nbits;
nbits += dist_enc->lengths[dist];
ebits = distance - dist_tbl[dist].base_dist;
bits |= ebits << nbits;
nbits += dist_tbl[dist].ebits;
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
}
return true;
}
بالطبع ، تعد كتابة كتل Huffman الديناميكية أكثر صعوبة لأنها تحتوي على ترميز خادع لشفرات litlen و dist. لتمثيل هذا الترميز ، نستخدم البنية التالية:typedef struct codelen_sym_t codelen_sym_t;
struct codelen_sym_t {
uint8_t sym;
uint8_t count;
};
أولاً ، نتخلص من ذيل أطوالها الصفرية لكلمات التشفير والشفرات ، ثم ننسخها في مصفوفة عادية للترميز اللاحق. لا يمكننا تجاهل جميع الأصفار: من المستحيل ترميز كتلة Deflate إذا لم يكن هناك رمز dist واحد. من المستحيل أيضًا أن يكون لديك أقل من 257 رمز litlen ، ولكن نظرًا لأن لدينا دائمًا علامة نهاية البايت ، فسيكون هناك دائمًا رمز غير صفري لحرف 256.
static size_t encode_dist_litlen_lens(const uint8_t *litlen_lens,
const uint8_t *dist_lens,
codelen_sym_t *encoded,
size_t *num_litlen_lens,
size_t *num_dist_lens)
{
size_t i, n;
uint8_t lens[LITLEN_MAX + 1 + DISTSYM_MAX + 1];
*num_litlen_lens = LITLEN_MAX + 1;
*num_dist_lens = DISTSYM_MAX + 1;
assert(litlen_lens[LITLEN_EOB] != 0 && "EOB len should be non-zero.");
while (litlen_lens[*num_litlen_lens - 1] == 0) {
(*num_litlen_lens)--;
}
assert(*num_litlen_lens >= MIN_LITLEN_LENS);
while (dist_lens[*num_dist_lens - 1] == 0 && *num_dist_lens > 1) {
(*num_dist_lens)--;
}
assert(*num_dist_lens >= MIN_DIST_LENS);
n = 0;
for (i = 0; i < *num_litlen_lens; i++) {
lens[n++] = litlen_lens[i];
}
for (i = 0; i < *num_dist_lens; i++) {
lens[n++] = dist_lens[i];
}
return encode_lens(lens, n, encoded);
}
بعد إضافة أطوال الكود إلى مصفوفة واحدة ، نقوم بإجراء الترميز باستخدام أحرف خاصة لتشغيل نفس أطوال الكود.
static size_t encode_lens(const uint8_t *lens, size_t n, codelen_sym_t *encoded)
{
size_t i, j, num_encoded;
uint8_t count;
i = 0;
num_encoded = 0;
while (i < n) {
if (lens[i] == 0) {
for (j = i; j < min(n, i + CODELEN_ZEROS2_MAX) &&
lens[j] == 0; j++);
count = (uint8_t)(j - i);
if (count < CODELEN_ZEROS_MIN) {
encoded[num_encoded++].sym = 0;
i++;
continue;
}
if (count <= CODELEN_ZEROS_MAX) {
assert(count >= CODELEN_ZEROS_MIN &&
count <= CODELEN_ZEROS_MAX);
encoded[num_encoded].sym = CODELEN_ZEROS;
encoded[num_encoded++].count = count;
} else {
assert(count >= CODELEN_ZEROS2_MIN &&
count <= CODELEN_ZEROS2_MAX);
encoded[num_encoded].sym = CODELEN_ZEROS2;
encoded[num_encoded++].count = count;
}
i = j;
continue;
}
encoded[num_encoded++].sym = lens[i++];
for (j = i; j < min(n, i + CODELEN_COPY_MAX) &&
lens[j] == lens[i - 1]; j++);
count = (uint8_t)(j - i);
if (count >= CODELEN_COPY_MIN) {
assert(count >= CODELEN_COPY_MIN &&
count <= CODELEN_COPY_MAX);
encoded[num_encoded].sym = CODELEN_COPY;
encoded[num_encoded++].count = count;
i = j;
continue;
}
}
return num_encoded;
}
سيتم تسجيل الأحرف المستخدمة للتشفير باستخدام كود Huffman - codelen. تتم كتابة أطوال كلمات التشفير من كود الكودلن إلى الكتلة بترتيب معين بحيث من المرجح أن تنتهي أطوال الصفر في النهاية. فيما يلي دالة تحسب عدد الأطوال التي يجب كتابتها:static const int codelen_lengths_order[19] =
{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
size_t count_codelen_lens(const uint8_t *codelen_lens)
{
size_t n = MAX_CODELEN_LENS;
while (codelen_lens[codelen_lengths_order[n - 1]] == 0) {
n--;
}
assert(n >= MIN_CODELEN_LENS && n <= MAX_CODELEN_LENS);
return n;
}
لنفترض أننا قمنا بالفعل بتعيين رموز litlen و dist ، وقمنا بإعداد ترميز أطوال كلمات الشفرة الخاصة بهم ، ورمز لهذه الأطوال. الآن يمكننا كتابة كتلة هوفمان ديناميكية:static bool write_dynamic_block(deflate_state_t *s, bool final,
size_t num_litlen_lens, size_t num_dist_lens,
size_t num_codelen_lens,
const huffman_encoder_t *codelen_enc,
const codelen_sym_t *encoded_lens,
size_t num_encoded_lens,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t i;
uint8_t codelen, sym;
size_t nbits;
uint64_t bits, hlit, hdist, hclen, count;
bits = (0x2 << 1) | final;
nbits = 3;
hlit = num_litlen_lens - MIN_LITLEN_LENS;
bits |= hlit << nbits;
nbits += 5;
hdist = num_dist_lens - MIN_DIST_LENS;
bits |= hdist << nbits;
nbits += 5;
hclen = num_codelen_lens - MIN_CODELEN_LENS;
bits |= hclen << nbits;
nbits += 4;
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
for (i = 0; i < num_codelen_lens; i++) {
codelen = codelen_enc->lengths[codelen_lengths_order[i]];
if (!ostream_write(&s->os, codelen, 3)) {
return false;
}
}
for (i = 0; i < num_encoded_lens; i++) {
sym = encoded_lens[i].sym;
bits = codelen_enc->codewords[sym];
nbits = codelen_enc->lengths[sym];
count = encoded_lens[i].count;
if (sym == CODELEN_COPY) {
bits |= (count - CODELEN_COPY_MIN) << nbits;
nbits += 2;
} else if (sym == CODELEN_ZEROS) {
bits |= (count - CODELEN_ZEROS_MIN) << nbits;
nbits += 3;
} else if (sym == CODELEN_ZEROS2) {
bits |= (count - CODELEN_ZEROS2_MIN) << nbits;
nbits += 7;
}
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
}
return write_huffman_block(s, litlen_enc, dist_enc);
}
لكل كتلة ، نريد استخدام النوع الذي يتطلب أقل عدد من البتات. يمكن حساب طول الكتلة غير المضغوطة بسرعة:
static size_t uncomp_block_len(const deflate_state_t *s)
{
size_t bit_pos, padding;
bit_pos = ostream_bit_pos(&s->os) + 3;
padding = round_up(bit_pos, 8) - bit_pos;
return 3 + padding + 2 * 16 + s->block_len_bytes * 8;
}
بالنسبة إلى الكتل المشفرة لـ Huffman ، يمكنك حساب طول الجسم باستخدام ترددات litlen- و dist- الترددات للأحرف وأطوال الكود:
static size_t huffman_block_body_len(const deflate_state_t *s,
const uint8_t *litlen_lens,
const uint8_t *dist_lens)
{
size_t i, freq, len;
len = 0;
for (i = 0; i <= LITLEN_MAX; i++) {
freq = s->litlen_freqs[i];
len += litlen_lens[i] * freq;
if (i >= LITLEN_TBL_OFFSET) {
len += litlen_tbl[i - LITLEN_TBL_OFFSET].ebits * freq;
}
}
for (i = 0; i <= DISTSYM_MAX; i++) {
freq = s->dist_freqs[i];
len += dist_lens[i] * freq;
len += dist_tbl[i].ebits * freq;
}
return len;
}
الطول الكلي للكتلة الثابتة هو 3 بتات من الرأس بالإضافة إلى طول الجسم. يتطلب حساب حجم رأس كتلة ديناميكية المزيد من العمل:
static size_t dyn_block_len(const deflate_state_t *s, size_t num_codelen_lens,
const uint16_t *codelen_freqs,
const huffman_encoder_t *codelen_enc,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t len, i, freq;
len = 3;
len += 5 + 5 + 4;
len += 3 * num_codelen_lens;
for (i = 0; i < MAX_CODELEN_LENS; i++) {
freq = codelen_freqs[i];
len += codelen_enc->lengths[i] * freq;
if (i == CODELEN_COPY) {
len += 2 * freq;
} else if (i == CODELEN_ZEROS) {
len += 3 * freq;
} else if (i == CODELEN_ZEROS2) {
len += 7 * freq;
}
}
return len + huffman_block_body_len(s, litlen_enc->lengths,
dist_enc->lengths);
}
الآن سنجمع كل شيء معًا وننشئ الوظيفة الرئيسية لكتابة الكتل:
static bool write_block(deflate_state_t *s, bool final)
{
size_t old_bit_pos, uncomp_len, static_len, dynamic_len;
huffman_encoder_t dyn_litlen_enc, dyn_dist_enc, codelen_enc;
size_t num_encoded_lens, num_litlen_lens, num_dist_lens;
codelen_sym_t encoded_lens[LITLEN_MAX + 1 + DISTSYM_MAX + 1];
uint16_t codelen_freqs[MAX_CODELEN_LENS] = {0};
size_t num_codelen_lens;
size_t i;
old_bit_pos = ostream_bit_pos(&s->os);
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
assert(s->litlen_freqs[LITLEN_EOB] == 0);
s->block[s->block_len ].distance = 0;
s->block[s->block_len++].u.lit = LITLEN_EOB;
s->litlen_freqs[LITLEN_EOB] = 1;
uncomp_len = uncomp_block_len(s);
static_len = 3 + huffman_block_body_len(s, fixed_litlen_lengths,
fixed_dist_lengths);
huffman_encoder_init(&dyn_litlen_enc, s->litlen_freqs,
LITLEN_MAX + 1, 15);
huffman_encoder_init(&dyn_dist_enc, s->dist_freqs, DISTSYM_MAX + 1, 15);
num_encoded_lens = encode_dist_litlen_lens(dyn_litlen_enc.lengths,
dyn_dist_enc.lengths,
encoded_lens,
&num_litlen_lens,
&num_dist_lens);
for (i = 0; i < num_encoded_lens; i++) {
codelen_freqs[encoded_lens[i].sym]++;
}
huffman_encoder_init(&codelen_enc, codelen_freqs, MAX_CODELEN_LENS, 7);
num_codelen_lens = count_codelen_lens(codelen_enc.lengths);
dynamic_len = dyn_block_len(s, num_codelen_lens, codelen_freqs,
&codelen_enc, &dyn_litlen_enc,
&dyn_dist_enc);
if (uncomp_len <= dynamic_len && uncomp_len <= static_len) {
if (!write_uncomp_block(s, final)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == uncomp_len);
} else if (static_len <= dynamic_len) {
if (!write_static_block(s, final)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == static_len);
} else {
if (!write_dynamic_block(s, final, num_litlen_lens,
num_dist_lens, num_codelen_lens,
&codelen_enc, encoded_lens,
num_encoded_lens, &dyn_litlen_enc,
&dyn_dist_enc)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == dynamic_len);
}
return true;
}
أخيرًا ، يجب على البادئ لعملية الضغط بأكملها تعيين الحالة الأولية وبدء ضغط Lempel-Ziv وكتابة الكتلة الناتجة:
bool hwdeflate(const uint8_t *src, size_t src_len, uint8_t *dst,
size_t dst_cap, size_t *dst_used)
{
deflate_state_t s;
ostream_init(&s.os, dst, dst_cap);
reset_block(&s);
s.block_src = src;
if (!lz77_compress(src, src_len, &lit_callback,
&backref_callback, &s)) {
return false;
}
if (!write_block(&s, true)) {
return false;
}
assert(s.block_src + s.block_len_bytes == src + src_len);
*dst_used = ostream_bytes_written(&s.os);
return true;
}
تنسيق ملف مضغوط
أعلاه ، درسنا كيف يعمل ضغط الانكماش المستخدم في ملفات Zip. ماذا عن تنسيق الملف نفسه؟ في هذا الجزء ، سوف ندرس بالتفصيل هيكلها وتنفيذها. متاح في قانون zip.h و zip.c .نظرة عامة
يتم وصف تنسيق الملف في ملاحظة تطبيق PKZip :- يحتوي كل ملف أو عنصر أرشفة في ملف مضغوط على رأس ملف محلي يحتوي على بيانات تعريف حول العنصر.
- . , , , Zip-.
- , . , . Zip-.
يتم ضغط كل عنصر أرشيف وتخزينه بشكل فردي. وهذا يعني أنه حتى في حالة وجود تطابقات بين الملفات الموجودة في الأرشيف ، فلن يتم أخذها في الاعتبار لتحسين الضغط.يسمح لك موقع الكتالوج المركزي في النهاية بإكمال الأرشيف تدريجيًا. أثناء ضغط عناصر الملف ، تتم إضافتها إلى الأرشيف. يتم تسجيل الفهرس بعد جميع الأحجام المضغوطة ، مما يسمح لك بمعرفة تعويضات جميع الملفات. تعد إضافة الملفات إلى أرشيف موجود أمرًا سهلاً للغاية ، حيث يتم وضعها بعد العنصر الأخير ، ويتم استبدال الدليل المركزي.كانت القدرة على إنشاء المحفوظات تدريجياً مهمة بشكل خاص لنشر المعلومات على العديد من الأقراص أو المجلدات المرنة. أثناء ضغطه ، اقترح PKZip على المستخدمين إدخال أقراص جديدة ، وكتابة الدليل المركزي إلى آخر (آخر). لفك ضغط أرشيف متعدد المجلدات ، طلب PKZip أولاً من القرص المرن الأخير أن يكتب لقراءة الدليل المركزي ، ثم بقية القرص المرن المطلوب لاستخراج الملفات المطلوبة.قد يفاجئك هذا ، ولكن لم تكن هناك قاعدة تحظر وجود ملفات متعددة بنفس الاسم في الأرشيف. يمكن أن يؤدي هذا إلى الكثير من الارتباك عند التفريغ: إذا كان هناك العديد من الملفات التي تحمل نفس الاسم ، فما الملف الذي يجب عليك تفريغه؟ وهذا بدوره قد يؤدي إلى مشاكل أمنية. بسبب خطأ "المفتاح الرئيسي" في Android (CVE-2013-4787 ، الشرائح و الفيديو من التقرير على القبعة السوداء) للمهاجم تجاوز الشيكات لل توقيع التشفير نظام التشغيل عند تثبيت البرامج. يتم توزيع برامج Android في ملفات APK ، وهي ملفات Zip. كما اتضح ، إذا احتوى ملف APK على عدة ملفات بالاسم نفسه ، حدد رمز التحقق من التوقيع الملف الأخير بنفس الاسم ، وحدد المثبت الملف الأول ، أي أنه لم يتم إجراء التحقق. بمعنى آخر ، فإن هذا الاختلاف الصغير بين المكتبتين Zip جعل من الممكن تجاوز نموذج أمان نظام التشغيل بالكامل.على عكس معظم التنسيقات ، يجب ألا تبدأ الملفات المضغوطة برقم توقيع أو سحري. بشكل عام ، لا يُشار إلى أن ملف Zip يجب أن يبدأ بأي طريقة محددة ، مما يسمح لك بسهولة بإنشاء ملفات صالحة كملف Zip وتنسيق مختلف - ملفات متعددة اللغات . على سبيل المثال ، عادةً ما تكون أرشيفات Zip ذاتية الاستخراج (على سبيل المثال ، pkz204g.exe ) قابلة للتنفيذ وملفات Zip: الجزء الأول قابل للتنفيذ ، متبوعًا بملف Zip (الذي يتم تفريغه بواسطة الجزء القابل للتنفيذ). يمكن لنظام التشغيل تنفيذه كملف قابل للتنفيذ ، لكن برنامج Zip سيفتحه كملف Zip. قد تتسبب هذه الميزة في عدم طلب التوقيع في بداية الملف.على الرغم من أن هذه الملفات متعددة اللغات ذكية ، إلا أنها يمكن أن تؤدي إلى مشاكل أمنية لأنها يمكن أن تخدع البرامج التي تحاول تحديد محتويات الملف وتسمح أيضًا بتسليم تعليمات برمجية ضارة في مكان يحتوي على ملفات من أنواع مختلفة. على سبيل المثال ، يستغل ملفات GIFAR المستخدمة ، والتي هي في نفس الوقت صور GIF صالحة وأرشيفات Java (JAR ، وهو نوع من ملفات Zip). لمزيد من المعلومات حول هذه المشكلة ، راجع المقالة إساءة استخدام تنسيقات الملفات (بدءًا من الصفحة 18).كما سنرى أدناه ، تستخدم ملفات Zip حقول 32 بت للإزاحة والأحجام للحد من حجم الأرشيف وعناصره إلى أربعة غيغابايت. في ملاحظة التطبيق 4.5أضافت PKWare ملحقات تنسيق تسمح باستخدام إزاحات وأحجام 64 بت. الملفات التي تستخدم هذه الامتدادات بتنسيق Zip64 ، لكننا لن نفكر فيها.هياكل البيانات
نهاية إدخال الدليل المركزي
عادةً ما يتم استخدام نهاية إدخال الدليل المركزي (EOCDR) كنقطة بداية لقراءة ملف مضغوط. يحتوي على موقع الدليل المركزي وحجمه ، بالإضافة إلى تعليقات اختيارية حول الأرشيف بأكمله.في الملفات المضغوطة التي احتلت العديد من الأقراص - أو وحدات التخزين - يحتوي EOCDR أيضًا على معلومات حول القرص الذي نستخدمه حاليًا ، وعلى أي قرص يبدأ الدليل المركزي ، وما إلى ذلك. اليوم ، نادرًا ما يتم استخدام هذه الوظيفة ، ولا يعالج الرمز في هذه المقالة مثل هذه الملفات.يتم تحديد EOCDR بالتوقيع "P" "K" ، متبوعًا بالبايتين 5 و 6. ويتبعه الهيكل أدناه ، ويتم تخزين الأرقام وفقًا لمبدأ الحد الأدنى:
struct eocdr {
uint16_t disk_nbr;
uint16_t cd_start_disk;
uint16_t disk_cd_entries;
uint16_t cd_entries;
uint32_t cd_size;
uint32_t cd_offset;
uint16_t comment_len;
const uint8_t *comment;
};
يجب وضع EOCDR في نهاية الملف. ولكن نظرًا لأنه قد يكون هناك تعليق بطول 16 بت تعسفي في ذيله ، فقد يكون من الضروري العثور على موقف محدد:
#define READ16(p) ((p) += 2, read16le((p) - 2))
#define READ32(p) ((p) += 4, read32le((p) - 4))
#define EOCDR_BASE_SZ 22
#define EOCDR_SIGNATURE 0x06054b50
static bool find_eocdr(struct eocdr *r, const uint8_t *src, size_t src_len)
{
size_t comment_len;
const uint8_t *p;
uint32_t signature;
for (comment_len = 0; comment_len <= UINT16_MAX; comment_len++) {
if (src_len < EOCDR_BASE_SZ + comment_len) {
break;
}
p = &src[src_len - EOCDR_BASE_SZ - comment_len];
signature = READ32(p);
if (signature == EOCDR_SIGNATURE) {
r->disk_nbr = READ16(p);
r->cd_start_disk = READ16(p);
r->disk_cd_entries = READ16(p);
r->cd_entries = READ16(p);
r->cd_size = READ32(p);
r->cd_offset = READ32(p);
r->comment_len = READ16(p);
r->comment = p;
assert(p == &src[src_len - comment_len] &&
"All fields read.");
if (r->comment_len == comment_len) {
return true;
}
}
}
return false;
}
تسجيل EOCDR سهل. تقوم هذه الوظيفة بكتابة وإعادة عدد البايت المكتوب:
#define WRITE16(p, x) (write16le((p), (x)), (p) += 2)
#define WRITE32(p, x) (write32le((p), (x)), (p) += 4)
static size_t write_eocdr(uint8_t *dst, const struct eocdr *r)
{
uint8_t *p = dst;
WRITE32(p, EOCDR_SIGNATURE);
WRITE16(p, r->disk_nbr);
WRITE16(p, r->cd_start_disk);
WRITE16(p, r->disk_cd_entries);
WRITE16(p, r->cd_entries);
WRITE32(p, r->cd_size);
WRITE32(p, r->cd_offset);
WRITE16(p, r->comment_len);
assert(p - dst == EOCDR_BASE_SZ);
if (r->comment_len != 0) {
memcpy(p, r->comment, r->comment_len);
p += r->comment_len;
}
return (size_t)(p - dst);
}
رأس الملف المركزي
يتكون الدليل المركزي من رؤوس الملفات المركزية المكتوبة واحدة تلو الأخرى ، واحدة لكل عنصر أرشيف. يبدأ كل عنوان بالتوقيع "P" و "K" و 1 و 2 ، ثم يوجد مثل هذا الهيكل:#define EXT_ATTR_DIR (1U << 4)
#define EXT_ATTR_ARC (1U << 5)
struct cfh {
uint16_t made_by_ver;
uint16_t extract_ver;
uint16_t gp_flag;
uint16_t method;
uint16_t mod_time;
uint16_t mod_date;
uint32_t crc32;
uint32_t comp_size;
uint32_t uncomp_size;
uint16_t name_len;
uint16_t extra_len;
uint16_t comment_len;
uint16_t disk_nbr_start;
uint16_t int_attrs;
uint32_t ext_attrs;
uint32_t lfh_offset;
const uint8_t *name;
const uint8_t *extra;
const uint8_t *comment;
};
made_by_ver
و extract_ver
المعلومات حول ترميز OS ونسخة من البرنامج تستخدم لإضافة هذا البند، وكذلك التي تحتاج إلى الإصدار لاسترجاعها. تقوم البتات الثمانية الأكثر أهمية بترميز نظام التشغيل (على سبيل المثال ، 0 تعني DOS ، 3 تعني Unix ، 10 تعني Windows NTFS) ، والبتات الثمانية السفلية ترميز إصدار البرنامج. قم بتعيين القيمة العشرية إلى 20 ، مما يعني التوافق مع PKZip 2.0.gp_flag
يحتوي على أعلام مختلفة. نحن مهتمون:- بت 0 ، تشير إلى حقيقة تشفير العنصر (لن نعتبر ذلك) ؛
- والبتات 1 و 2 ، ترميز مستوى ضغط الانكماش (0 - عادي ، 1 - الحد الأقصى ، 2 - سريع ، 3 - سريع جدًا).
method
يشفر طريقة ضغط. 0 - البيانات غير مضغوطة ، 8 - Delate مطبقة. ترتبط القيم الأخرى بالخوارزميات القديمة أو الجديدة ، ولكن معظم Zip تستخدم هاتين القيمتين.mod_time
و mod_date
تتضمن تاريخ ووقت تم تعديل الملف، المشفرة في شكل MS-DOS . باستخدام هذا الرمز ، سنقوم بتحويل الطوابع الزمنية C المعتادة time_t
من وإلى تنسيق MS-DOS:
static time_t dos2ctime(uint16_t dos_date, uint16_t dos_time)
{
struct tm tm = {0};
tm.tm_sec = (dos_time & 0x1f) * 2;
tm.tm_min = (dos_time >> 5) & 0x3f;
tm.tm_hour = (dos_time >> 11);
tm.tm_mday = (dos_date & 0x1f);
tm.tm_mon = ((dos_date >> 5) & 0xf) - 1;
tm.tm_year = (dos_date >> 9) + 80;
tm.tm_isdst = -1;
return mktime(&tm);
}
static void ctime2dos(time_t t, uint16_t *dos_date, uint16_t *dos_time)
{
struct tm *tm = localtime(&t);
*dos_time = 0;
*dos_time |= tm->tm_sec / 2;
*dos_time |= tm->tm_min << 5;
*dos_time |= tm->tm_hour << 11;
*dos_date = 0;
*dos_date |= tm->tm_mday;
*dos_date |= (tm->tm_mon + 1) << 5;
*dos_date |= (tm->tm_year - 80) << 9;
}
crc32
يحتوي الحقل على قيمة الرمز الزائد الدوري للبيانات غير المضغوطة. يتم استخدامه للتحقق من سلامة البيانات بعد استرجاعها. التنفيذ هنا: crc32.c .comp_size
و uncomp_size
احتواء حجم مضغوط وغير مضغوط للبيانات ملف البند. تحتوي الحقول الثلاثة التالية على طول الاسم والتعليق والبيانات الإضافية التي تلي العنوان مباشرة. disk_nbr_start
مصممة للأرشيفات باستخدام أقراص متعددة.int_attrs
و ext_attrs
وصف السمات الداخلية والخارجية من الملف. تتعلق الملفات الداخلية بمحتويات الملف ، على سبيل المثال ، يشير البت المنخفض إلى ما إذا كان الملف يحتوي على نص فقط. تشير السمات الخارجية إلى ما إذا كان الملف مخفيًا ، أو للقراءة فقط ، وما إلى ذلك. يعتمد محتوى هذه الحقول على نظام التشغيل ، على وجه الخصوص ، علىmade_by_ver
. في DOS ، تحتوي البتات السفلية 8 على بايت سمة الملف ، والتي يمكن الحصول عليها من Int 21 / AX = 4300h استدعاء النظام . على سبيل المثال ، يعني البت 4 أنه دليل ، والبت 5 يعني أنه تم تعيين سمة "الأرشيف" (صحيح لمعظم الملفات في DOS). بقدر ما أفهم ، من أجل التوافق ، يتم تعيين هذه البتات بالمثل في أنظمة تشغيل أخرى. في Unix ، تحتوي البتات الـ 16 العالية في هذا الحقل على بتات وضع الملف التي يتم إرجاعها بواسطة stat (2) in st_mode
.lfh_offset
يخبرنا عن مكان البحث عن رأس الملف المحلي. name
- اسم الملف (C-line) و comment
- تعليق اختياري لعنصر الأرشيف هذا (C-line). extra
قد تحتوي على بيانات إضافية اختيارية مثل معلومات حول مالك ملف Unix أو تاريخ ووقت أكثر دقة للتغيير أو حقول Zip64.تستخدم هذه الوظيفة لقراءة الرؤوس المركزية للملفات:
#define CFH_BASE_SZ 46
#define CFH_SIGNATURE 0x02014b50
static bool read_cfh(struct cfh *cfh, const uint8_t *src, size_t src_len,
size_t offset)
{
const uint8_t *p;
uint32_t signature;
if (offset > src_len || src_len - offset < CFH_BASE_SZ) {
return false;
}
p = &src[offset];
signature = READ32(p);
if (signature != CFH_SIGNATURE) {
return false;
}
cfh->made_by_ver = READ16(p);
cfh->extract_ver = READ16(p);
cfh->gp_flag = READ16(p);
cfh->method = READ16(p);
cfh->mod_time = READ16(p);
cfh->mod_date = READ16(p);
cfh->crc32 = READ32(p);
cfh->comp_size = READ32(p);
cfh->uncomp_size = READ32(p);
cfh->name_len = READ16(p);
cfh->extra_len = READ16(p);
cfh->comment_len = READ16(p);
cfh->disk_nbr_start = READ16(p);
cfh->int_attrs = READ16(p);
cfh->ext_attrs = READ32(p);
cfh->lfh_offset = READ32(p);
cfh->name = p;
cfh->extra = cfh->name + cfh->name_len;
cfh->comment = cfh->extra + cfh->extra_len;
assert(p == &src[offset + CFH_BASE_SZ] && "All fields read.");
if (src_len - offset - CFH_BASE_SZ <
cfh->name_len + cfh->extra_len + cfh->comment_len) {
return false;
}
return true;
}
static size_t write_cfh(uint8_t *dst, const struct cfh *cfh)
{
uint8_t *p = dst;
WRITE32(p, CFH_SIGNATURE);
WRITE16(p, cfh->made_by_ver);
WRITE16(p, cfh->extract_ver);
WRITE16(p, cfh->gp_flag);
WRITE16(p, cfh->method);
WRITE16(p, cfh->mod_time);
WRITE16(p, cfh->mod_date);
WRITE32(p, cfh->crc32);
WRITE32(p, cfh->comp_size);
WRITE32(p, cfh->uncomp_size);
WRITE16(p, cfh->name_len);
WRITE16(p, cfh->extra_len);
WRITE16(p, cfh->comment_len);
WRITE16(p, cfh->disk_nbr_start);
WRITE16(p, cfh->int_attrs);
WRITE32(p, cfh->ext_attrs);
WRITE32(p, cfh->lfh_offset);
assert(p - dst == CFH_BASE_SZ);
if (cfh->name_len != 0) {
memcpy(p, cfh->name, cfh->name_len);
p += cfh->name_len;
}
if (cfh->extra_len != 0) {
memcpy(p, cfh->extra, cfh->extra_len);
p += cfh->extra_len;
}
if (cfh->comment_len != 0) {
memcpy(p, cfh->comment, cfh->comment_len);
p += cfh->comment_len;
}
return (size_t)(p - dst);
}
رأس ملف محلي
يسبق بيانات كل عنصر أرشفي رأس ملف محلي ، والذي يكرر معظم المعلومات من الرأس المركزي.ربما تم إدخال ازدواجية البيانات في الرؤوس المركزية والمحلية بحيث لا يحتفظ PKZip بالدليل المركزي بأكمله في الذاكرة عند تفريغه. بدلاً من ذلك ، أثناء استخراج كل ملف ، يمكن قراءة اسمه ومعلومات أخرى من العنوان المحلي. بالإضافة إلى ذلك ، تفيد الرؤوس المحلية في استرداد الملفات من أرشيفات Zip التي يكون فيها الدليل المركزي مفقودًا أو تالفًا.ومع ذلك ، فإن هذا التكرار هو أيضًا المصدر الرئيسي لعدم اليقين. على سبيل المثال ، ماذا يحدث إذا لم تتطابق أسماء الملفات في الرؤوس المركزية والمحلية؟ غالبًا ما يؤدي هذا إلى الأخطاء ومشكلات الأمان.لا يتم تكرار جميع المعلومات من العنوان المركزي. على سبيل المثال ، الحقول ذات سمات الملف. بالإضافة إلى ذلك ، إذا تم تحديد البت الثالث الأقل أهمية gp_flags
(CRC-32) ، فسيتم إعادة تعيين الحقول المضغوطة وغير المضغوطة إلى الصفر ، ويمكن العثور على هذه المعلومات في كتلة واصف البيانات بعد بيانات الملف نفسه (لن نأخذها بعين الاعتبار). هذا يسمح لك بتسجيل رأس محلي قبل أن يعرف حجم ملف العنصر أو إلى أي حجم سيتم ضغطه.يبدأ العنوان المحلي بالتوقيع "P" و "K" و 3 و 4 ، ثم هناك مثل هذا الهيكل:
struct lfh {
uint16_t extract_ver;
uint16_t gp_flag;
uint16_t method;
uint16_t mod_time;
uint16_t mod_date;
uint32_t crc32;
uint32_t comp_size;
uint32_t uncomp_size;
uint16_t name_len;
uint16_t extra_len;
const uint8_t *name;
const uint8_t *extra;
};
تقوم هذه الوظائف بقراءة وكتابة العناوين المحلية ، مثل هياكل البيانات الأخرى:
#define LFH_BASE_SZ 30
#define LFH_SIGNATURE 0x04034b50
static bool read_lfh(struct lfh *lfh, const uint8_t *src, size_t src_len,
size_t offset)
{
const uint8_t *p;
uint32_t signature;
if (offset > src_len || src_len - offset < LFH_BASE_SZ) {
return false;
}
p = &src[offset];
signature = READ32(p);
if (signature != LFH_SIGNATURE) {
return false;
}
lfh->extract_ver = READ16(p);
lfh->gp_flag = READ16(p);
lfh->method = READ16(p);
lfh->mod_time = READ16(p);
lfh->mod_date = READ16(p);
lfh->crc32 = READ32(p);
lfh->comp_size = READ32(p);
lfh->uncomp_size = READ32(p);
lfh->name_len = READ16(p);
lfh->extra_len = READ16(p);
lfh->name = p;
lfh->extra = lfh->name + lfh->name_len;
assert(p == &src[offset + LFH_BASE_SZ] && "All fields read.");
if (src_len - offset - LFH_BASE_SZ < lfh->name_len + lfh->extra_len) {
return false;
}
return true;
}
static size_t write_lfh(uint8_t *dst, const struct lfh *lfh)
{
uint8_t *p = dst;
WRITE32(p, LFH_SIGNATURE);
WRITE16(p, lfh->extract_ver);
WRITE16(p, lfh->gp_flag);
WRITE16(p, lfh->method);
WRITE16(p, lfh->mod_time);
WRITE16(p, lfh->mod_date);
WRITE32(p, lfh->crc32);
WRITE32(p, lfh->comp_size);
WRITE32(p, lfh->uncomp_size);
WRITE16(p, lfh->name_len);
WRITE16(p, lfh->extra_len);
assert(p - dst == LFH_BASE_SZ);
if (lfh->name_len != 0) {
memcpy(p, lfh->name, lfh->name_len);
p += lfh->name_len;
}
if (lfh->extra_len != 0) {
memcpy(p, lfh->extra, lfh->extra_len);
p += lfh->extra_len;
}
return (size_t)(p - dst);
}
تنفيذ Zip Read
باستخدام الوظائف المذكورة أعلاه ، نقوم بتنفيذ قراءة ملف Zip في الذاكرة ونحصل على مكرر للوصول إلى عناصر الأرشيف:typedef size_t zipiter_t;
typedef struct zip_t zip_t;
struct zip_t {
uint16_t num_members;
const uint8_t *comment;
uint16_t comment_len;
zipiter_t members_begin;
zipiter_t members_end;
const uint8_t *src;
size_t src_len;
};
bool zip_read(zip_t *zip, const uint8_t *src, size_t src_len)
{
struct eocdr eocdr;
struct cfh cfh;
struct lfh lfh;
size_t i, offset;
const uint8_t *comp_data;
zip->src = src;
zip->src_len = src_len;
if (!find_eocdr(&eocdr, src, src_len)) {
return false;
}
if (eocdr.disk_nbr != 0 || eocdr.cd_start_disk != 0 ||
eocdr.disk_cd_entries != eocdr.cd_entries) {
return false;
}
zip->num_members = eocdr.cd_entries;
zip->comment = eocdr.comment;
zip->comment_len = eocdr.comment_len;
offset = eocdr.cd_offset;
zip->members_begin = offset;
for (i = 0; i < eocdr.cd_entries; i++) {
if (!read_cfh(&cfh, src, src_len, offset)) {
return false;
}
if (cfh.gp_flag & 1) {
return false;
}
if (cfh.method != ZIP_STORED && cfh.method != ZIP_DEFLATED) {
return false;
}
if (cfh.method == ZIP_STORED &&
cfh.uncomp_size != cfh.comp_size) {
return false;
}
if (cfh.disk_nbr_start != 0) {
return false;
}
if (memchr(cfh.name, '\0', cfh.name_len) != NULL) {
return false;
}
if (!read_lfh(&lfh, src, src_len, cfh.lfh_offset)) {
return false;
}
comp_data = lfh.extra + lfh.extra_len;
if (cfh.comp_size > src_len - (size_t)(comp_data - src)) {
return false;
}
offset += CFH_BASE_SZ + cfh.name_len + cfh.extra_len +
cfh.comment_len;
}
zip->members_end = offset;
return true;
}
كما ذكرت أعلاه ، فإن تكرارات العناصر هي مجرد إزاحة لرأس الملف المركزي الذي يمكنك من خلاله الوصول إلى بيانات العنصر:typedef enum { ZIP_STORED = 0, ZIP_DEFLATED = 8 } method_t;
typedef struct zipmemb_t zipmemb_t;
struct zipmemb_t {
const uint8_t *name;
uint16_t name_len;
time_t mtime;
uint32_t comp_size;
const uint8_t *comp_data;
method_t method;
uint32_t uncomp_size;
uint32_t crc32;
const uint8_t *comment;
uint16_t comment_len;
bool is_dir;
zipiter_t next;
};
zipmemb_t zip_member(const zip_t *zip, zipiter_t it)
{
struct cfh cfh;
struct lfh lfh;
bool ok;
zipmemb_t m;
assert(it >= zip->members_begin && it < zip->members_end);
ok = read_cfh(&cfh, zip->src, zip->src_len, it);
assert(ok);
ok = read_lfh(&lfh, zip->src, zip->src_len, cfh.lfh_offset);
assert(ok);
m.name = cfh.name;
m.name_len = cfh.name_len;
m.mtime = dos2ctime(cfh.mod_date, cfh.mod_time);
m.comp_size = cfh.comp_size;
m.comp_data = lfh.extra + lfh.extra_len;
m.method = cfh.method;
m.uncomp_size = cfh.uncomp_size;
m.crc32 = cfh.crc32;
m.comment = cfh.comment;
m.comment_len = cfh.comment_len;
m.is_dir = (cfh.ext_attrs & EXT_ATTR_DIR) != 0;
m.next = it + CFH_BASE_SZ +
cfh.name_len + cfh.extra_len + cfh.comment_len;
assert(m.next <= zip->members_end);
return m;
}
تنفيذ سجل Zip
لكتابة ملف مضغوط إلى المخزن المؤقت للذاكرة ، تحتاج أولاً إلى معرفة مقدار الذاكرة المخصصة له. وبما أننا لا نعرف مقدار البيانات التي سنضغطها قبل أن نحاول الكتابة ، فإننا نحسب الحد الأعلى بناءً على أحجام العناصر غير المضغوطة:
uint32_t zip_max_size(uint16_t num_memb, const char *const *filenames,
const uint32_t *file_sizes, const char *comment)
{
size_t comment_len, name_len;
uint64_t total;
uint16_t i;
comment_len = (comment == NULL ? 0 : strlen(comment));
if (comment_len > UINT16_MAX) {
return 0;
}
total = EOCDR_BASE_SZ + comment_len;
for (i = 0; i < num_memb; i++) {
assert(filenames[i] != NULL);
name_len = strlen(filenames[i]);
if (name_len > UINT16_MAX) {
return 0;
}
total += CFH_BASE_SZ + name_len;
total += LFH_BASE_SZ + name_len;
total += file_sizes[i];
}
if (total > UINT32_MAX) {
return 0;
}
return (uint32_t)total;
}
يكتب هذا الرمز الملف المضغوط باستخدام ضغط انكماش كل عنصر ، مما يقلل حجمه:
uint32_t zip_write(uint8_t *dst, uint16_t num_memb,
const char *const *filenames,
const uint8_t *const *file_data,
const uint32_t *file_sizes,
const time_t *mtimes,
const char *comment,
void (*callback)(const char *filename, uint32_t size,
uint32_t comp_size))
{
uint16_t i;
uint8_t *p;
struct eocdr eocdr;
struct cfh cfh;
struct lfh lfh;
bool ok;
uint16_t name_len;
uint8_t *data_dst;
size_t comp_sz;
uint32_t lfh_offset, cd_offset, eocdr_offset;
p = dst;
for (i = 0; i < num_memb; i++) {
assert(filenames[i] != NULL);
assert(strlen(filenames[i]) <= UINT16_MAX);
name_len = (uint16_t)strlen(filenames[i]);
data_dst = p + LFH_BASE_SZ + name_len;
if (hwdeflate(file_data[i], file_sizes[i], data_dst,
file_sizes[i], &comp_sz) &&
comp_sz < file_sizes[i]) {
lfh.method = ZIP_DEFLATED;
assert(comp_sz <= UINT32_MAX);
lfh.comp_size = (uint32_t)comp_sz;
} else {
memcpy(data_dst, file_data[i], file_sizes[i]);
lfh.method = ZIP_STORED;
lfh.comp_size = file_sizes[i];
}
if (callback != NULL) {
callback(filenames[i], file_sizes[i], lfh.comp_size);
}
lfh.extract_ver = (0 << 8) | 20;
lfh.gp_flag = (lfh.method == ZIP_DEFLATED ? (0x1 << 1) : 0x0);
ctime2dos(mtimes[i], &lfh.mod_date, &lfh.mod_time);
lfh.crc32 = crc32(file_data[i], file_sizes[i]);
lfh.uncomp_size = file_sizes[i];
lfh.name_len = name_len;
lfh.extra_len = 0;
lfh.name = (const uint8_t*)filenames[i];
p += write_lfh(p, &lfh);
p += lfh.comp_size;
}
assert(p - dst <= UINT32_MAX);
cd_offset = (uint32_t)(p - dst);
lfh_offset = 0;
for (i = 0; i < num_memb; i++) {
ok = read_lfh(&lfh, dst, SIZE_MAX, lfh_offset);
assert(ok);
cfh.made_by_ver = lfh.extract_ver;
cfh.extract_ver = lfh.extract_ver;
cfh.gp_flag = lfh.gp_flag;
cfh.method = lfh.method;
cfh.mod_time = lfh.mod_time;
cfh.mod_date = lfh.mod_date;
cfh.crc32 = lfh.crc32;
cfh.comp_size = lfh.comp_size;
cfh.uncomp_size = lfh.uncomp_size;
cfh.name_len = lfh.name_len;
cfh.extra_len = 0;
cfh.comment_len = 0;
cfh.disk_nbr_start = 0;
cfh.int_attrs = 0;
cfh.ext_attrs = EXT_ATTR_ARC;
cfh.lfh_offset = lfh_offset;
cfh.name = lfh.name;
p += write_cfh(p, &cfh);
lfh_offset += LFH_BASE_SZ + lfh.name_len + lfh.comp_size;
}
assert(p - dst <= UINT32_MAX);
eocdr_offset = (uint32_t)(p - dst);
eocdr.disk_nbr = 0;
eocdr.cd_start_disk = 0;
eocdr.disk_cd_entries = num_memb;
eocdr.cd_entries = num_memb;
eocdr.cd_size = eocdr_offset - cd_offset;
eocdr.cd_offset = cd_offset;
eocdr.comment_len = (uint16_t)(comment == NULL ? 0 : strlen(comment));
eocdr.comment = (const uint8_t*)comment;
p += write_eocdr(p, &eocdr);
assert(p - dst <= zip_max_size(num_memb, filenames, file_sizes,
comment));
return (uint32_t)(p - dst);
}
هوزيب
الآن نحن نعرف كيفية قراءة وكتابة ملفات Zip ، وكيفية ضغط وفك ضغط البيانات المخزنة فيها. اكتب الآن برنامجًا مضغوطًا بسيطًا يحتوي على كل هذه الأدوات. الكود متاح في hwzip.c .سنستخدم ماكرو لمعالجة الأخطاء البسيطة والعديد من الوظائف الإضافية لتخصيص الذاكرة التي تم فحصها:#define PERROR_IF(cond, msg) if (cond) { perror(msg); exit(1); }
static void *xmalloc(size_t size)
{
void *ptr = malloc(size);
PERROR_IF(ptr == NULL, "malloc");
return ptr;
}
static void *xrealloc(void *ptr, size_t size)
{
ptr = realloc(ptr, size);
PERROR_IF(ptr == NULL, "realloc");
return ptr;
}
يتم استخدام الوظيفتين الأخريين لقراءة الملفات وكتابتها:static uint8_t *read_file(const char *filename, size_t *file_sz)
{
FILE *f;
uint8_t *buf;
size_t buf_cap;
f = fopen(filename, "rb");
PERROR_IF(f == NULL, "fopen");
buf_cap = 4096;
buf = xmalloc(buf_cap);
*file_sz = 0;
while (feof(f) == 0) {
if (buf_cap - *file_sz == 0) {
buf_cap *= 2;
buf = xrealloc(buf, buf_cap);
}
*file_sz += fread(&buf[*file_sz], 1, buf_cap - *file_sz, f);
PERROR_IF(ferror(f), "fread");
}
PERROR_IF(fclose(f) != 0, "fclose");
return buf;
}
static void write_file(const char *filename, const uint8_t *data, size_t n)
{
FILE *f;
f = fopen(filename, "wb");
PERROR_IF(f == NULL, "fopen");
PERROR_IF(fwrite(data, 1, n, f) != n, "fwrite");
PERROR_IF(fclose(f) != 0, "fclose");
}
يمكن لبرنامج Zip الخاص بنا تنفيذ ثلاث وظائف: عمل قائمة بمحتويات ملفات Zip واستخراجها ، بالإضافة إلى إنشاء ملفات Zip. الإدراج في أي مكان أبسط:static void list_zip(const char *filename)
{
uint8_t *zip_data;
size_t zip_sz;
zip_t z;
zipiter_t it;
zipmemb_t m;
printf("Listing ZIP archive: %s\n\n", filename);
zip_data = read_file(filename, &zip_sz);
if (!zip_read(&z, zip_data, zip_sz)) {
printf("Failed to parse ZIP file!\n");
exit(1);
}
if (z.comment_len != 0) {
printf("%.*s\n\n", (int)z.comment_len, z.comment);
}
for (it = z.members_begin; it != z.members_end; it = m.next) {
m = zip_member(&z, it);
printf("%.*s\n", (int)m.name_len, m.name);
}
printf("\n");
free(zip_data);
}
الاستخراج أكثر تعقيدًا قليلاً. سنستخدم الدوال الإضافية لإنهاء اسم الملف (لتمريره إليه fopen
) وتفريغه:static char *terminate_str(const char *str, size_t n)
{
char *p = xmalloc(n + 1);
memcpy(p, str, n);
p[n] = '\0';
return p;
}
static uint8_t *inflate_member(const zipmemb_t *m)
{
uint8_t *p;
size_t src_used, dst_used;
assert(m->method == ZIP_DEFLATED);
p = xmalloc(m->uncomp_size);
if (hwinflate(m->comp_data, m->comp_size, &src_used, p, m->uncomp_size,
&dst_used) != HWINF_OK) {
free(p);
return NULL;
}
if (src_used != m->comp_size || dst_used != m->uncomp_size) {
free(p);
return NULL;
}
return p;
}
سيتخطى برنامجنا أي عناصر أرشيف لها أدلة. يتم ذلك من أجل تجنب ما يسمى بهجمات اجتياز المسار : يتم استخدام أرشيف ضار لكتابة الملف من خارج الدليل المحدد من قبل المستخدم. اقرأ التفاصيل في الأسئلة المتداولة حول Info-ZIP .static void extract_zip(const char *filename)
{
uint8_t *zip_data;
size_t zip_sz;
zip_t z;
zipiter_t it;
zipmemb_t m;
char *tname;
uint8_t *inflated;
const uint8_t *uncomp_data;
printf("Extracting ZIP archive: %s\n\n", filename);
zip_data = read_file(filename, &zip_sz);
if (!zip_read(&z, zip_data, zip_sz)) {
printf("Failed to read ZIP file!\n");
exit(1);
}
if (z.comment_len != 0) {
printf("%.*s\n\n", (int)z.comment_len, z.comment);
}
for (it = z.members_begin; it != z.members_end; it = m.next) {
m = zip_member(&z, it);
if (m.is_dir) {
printf(" (Skipping dir: %.*s)\n",
(int)m.name_len, m.name);
continue;
}
if (memchr(m.name, '/', m.name_len) != NULL ||
memchr(m.name, '\\', m.name_len) != NULL) {
printf(" (Skipping file in dir: %.*s)\n",
(int)m.name_len, m.name);
continue;
}
assert(m.method == ZIP_STORED || m.method == ZIP_DEFLATED);
printf(" %s: %.*s",
m.method == ZIP_STORED ? "Extracting" : " Inflating",
(int)m.name_len, m.name);
fflush(stdout);
if (m.method == ZIP_STORED) {
assert(m.uncomp_size == m.comp_size);
inflated = NULL;
uncomp_data = m.comp_data;
} else {
inflated = inflate_member(&m);
if (inflated == NULL) {
printf("Error: inflation failed!\n");
exit(1);
}
uncomp_data = inflated;
}
if (crc32(uncomp_data, m.uncomp_size) != m.crc32) {
printf("Error: CRC-32 mismatch!\n");
exit(1);
}
tname = terminate_str((const char*)m.name, m.name_len);
write_file(tname, uncomp_data, m.uncomp_size);
printf("\n");
free(inflated);
free(tname);
}
printf("\n");
free(zip_data);
}
لإنشاء أرشيف مضغوط ، سنقرأ ملفات الإدخال ونطعمها zip_write
. نظرًا لأن مكتبة C القياسية لا تسمح لك بالحصول على وقت تعديل الملف ، فسوف نستخدم الوقت الحالي (أترك هذا كواجب منزلي لإصلاح هذه الميزة).void zip_callback(const char *filename, uint32_t size, uint32_t comp_size)
{
bool deflated = comp_size < size;
printf(" %s: %s", deflated ? "Deflated" : " Stored", filename);
if (deflated) {
printf(" (%u%%)", 100 - 100 * comp_size / size);
}
printf("\n");
}
static void create_zip(const char *zip_filename, const char *comment,
uint16_t n, const char *const *filenames)
{
time_t mtime;
time_t *mtimes;
uint8_t **file_data;
uint32_t *file_sizes;
size_t file_size, zip_size;
uint8_t *zip_data;
uint16_t i;
printf("Creating ZIP archive: %s\n\n", zip_filename);
if (comment != NULL) {
printf("%s\n\n", comment);
}
mtime = time(NULL);
file_data = xmalloc(sizeof(*file_data) * n);
file_sizes = xmalloc(sizeof(*file_sizes) * n);
mtimes = xmalloc(sizeof(*mtimes) * n);
for (i = 0; i < n; i++) {
file_data[i] = read_file(filenames[i], &file_size);
if (file_size >= UINT32_MAX) {
printf("%s is too large!\n", filenames[i]);
exit(1);
}
file_sizes[i] = (uint32_t)file_size;
mtimes[i] = mtime;
}
zip_size = zip_max_size(n, filenames, file_sizes, comment);
if (zip_size == 0) {
printf("zip writing not possible");
exit(1);
}
zip_data = xmalloc(zip_size);
zip_size = zip_write(zip_data, n, filenames,
(const uint8_t *const *)file_data,
file_sizes, mtimes, comment, zip_callback);
write_file(zip_filename, zip_data, zip_size);
printf("\n");
free(zip_data);
for (i = 0; i < n; i++) {
free(file_data[i]);
}
free(mtimes);
free(file_sizes);
free(file_data);
}
أخيرًا ، main
يتحقق من حجج سطر الأوامر ويقرر ما يجب فعله:static void print_usage(const char *argv0)
{
printf("Usage:\n\n");
printf(" %s list <zipfile>\n", argv0);
printf(" %s extract <zipfile>\n", argv0);
printf(" %s create <zipfile> [-c <comment>] <files...>\n", argv0);
printf("\n");
}
int main(int argc, char **argv) {
printf("\n");
printf("HWZIP " VERSION " -- A very simple ZIP program ");
printf("from https://www.hanshq.net/zip.html\n");
printf("\n");
if (argc == 3 && strcmp(argv[1], "list") == 0) {
list_zip(argv[2]);
} else if (argc == 3 && strcmp(argv[1], "extract") == 0) {
extract_zip(argv[2]);
} else if (argc >= 3 && strcmp(argv[1], "create") == 0) {
if (argc >= 5 && strcmp(argv[3], "-c") == 0) {
create_zip(argv[2], argv[4], (uint16_t)(argc - 5),
(const char *const *)&argv[5]);
} else {
create_zip(argv[2], NULL, (uint16_t)(argc - 3),
(const char *const *)&argv[3]);
}
} else {
print_usage(argv[0]);
return 1;
}
return 0;
}
تعليمات التجميع
تتوفر مجموعة كاملة من ملفات المصدر في hwzip-1.0.zip . كيفية تجميع HWZip تحت Linux أو Mac:$ clang generate_tables.c && ./a.out > tables.c
$ clang -O3 -DNDEBUG -march=native -o hwzip crc32.c deflate.c huffman.c \
hwzip.c lz77.c tables.c zip.c
في Windows ، في موجه أوامر المطور في Visual Studio (إذا لم يكن لديك Visual Studio ، فقم بتنزيل أدوات البناء ):cl /TC generate_tables.c && generate_tables > tables.c
cl /O2 /DNDEBUG /MT /Fehwzip.exe /TC crc32.c deflate.c huffman.c hwzip.c
lz77.c tables.c zip.c /link setargv.obj
Setargv.obj لتوسيع وسيطات سطر أوامر حرف البدل .)استنتاج
من المدهش كيف تتطور التكنولوجيا بسرعة وبطء. تم إنشاء تنسيق Zip قبل 30 عامًا استنادًا إلى التكنولوجيا من الخمسينات والسبعينات. وعلى الرغم من تغير الكثير منذ ذلك الحين ، إلا أن الملفات المضغوطة ، في الواقع ، ظلت كما هي ، وهي اليوم أكثر شيوعًا من أي وقت مضى. أعتقد أنه سيكون من المفيد الحصول على فهم جيد لكيفية عملهم.تمارين
- اجعل HWZip يسجل الوقت الذي يستغرقه كل ملف للتغيير ، بدلاً من الوقت الحالي الذي تم فيه إنشاء الأرشيف. استخدم stat (2) على Linux أو Mac و GetFileTime على Windows. أو أضف علامة سطر أوامر تسمح للمستخدم بتعيين وقت محدد لتغييرات الملف.
- gzip-. — , Deflate ( ). RFC 1952.
- Zip- . HWZip ,
read_file
mmap(2) Linux Mac CreateFileMapping Windows. - HWZip , Zip64. appnote.txt.