تنزيل FastLZ - تنزيل رمز المصدر FastLZ

FastLZ

كود مصدر C#

1.0.0

تنزيل

ملخص

Fastlz (ترخيص MIT) هو تنفيذ ANSI C/C90 لخوارزمية Lempel-Ziv 77 (LZ77) لضغط البيانات بدون فقدان. إنه مناسب لضغط سلسلة من النصوص/الفقرات ، أو تسلسل بيانات البكسل الخام ، أو أي كتل أخرى من البيانات مع الكثير من التكرار. ليس المقصود استخدامه على الصور ومقاطع الفيديو وتنسيقات البيانات الأخرى عادةً في شكل مضغوط مثالي.

التركيز على Fastlz هو ضغط سريع للغاية وإزالة الضغط ، والقيام بذلك على حساب نسبة الضغط. كتوضيح ، المقارنة مع Zlib عند ضغط ENWIK8 (أيضًا بمزيد من التفاصيل):

	نسبة	ضغط	إلغاء الضغط
fastlz	54.2 ٪	159 ميغابايت/ثانية	305 ميغابايت/ثانية
Zlib -1	42.3 ٪	50 ميجابايت/ثانية	184 ميغابايت/ثانية
Zlib -9	36.5 ٪	11 ميجابايت/ثانية	185 ميغابايت/ثانية

يتم استخدام Fastlz من قبل العديد من منتجات البرمجيات ، من عدد من الألعاب (مثل Death Stranding) إلى العديد من المشاريع مفتوحة المصدر (Godot Engine ، Facebook HHVM ، Apache Traffic Server ، Calligra Office ، OSV ، Netty ، إلخ). حتى أنه بمثابة أساس لمشاريع الضغط الأخرى مثل BLOSC.

للتطبيقات الأخرى لـ LZ77 المحاذاة البايت ، ألق نظرة على LZ4 ، Snappy ، الكثافة ، LZO ، LZF ، LZJB ، LZRW ، إلخ.

الاستخدام

يمكن استخدام Fastlz مباشرة في أي تطبيقات C/C ++. للغات/بيئات البرمجة الأخرى ، استخدم الربط المقابل:

الصدأ ، متوفر على الصناديق: cargo install fastlz
بيثون ، متاح على PYPI: pip install fastlz
JavaScript ، متاح على NPM: npm install fastlz
روبي ، متاح على Rubygems: gem install fastlz
لوا عبر github.com/oneoo/lua-fastlz

يتكون Fastlz من ملفين فقط: fastlz.h و fastlz.c . فقط أضف هذه الملفات إلى مشروعك من أجل استخدام FastLz. للحصول على المعلومات التفصيلية على واجهة برمجة التطبيقات لإجراء الضغط وإزالة الضغط ، انظر fastlz.h .

بالنسبة لمستخدمي VCPKG ، يتوفر Fastlz بالفعل: vcpkg install fastlz .

يتم تضمين ضاغط ملف بسيط يسمى 6pack كمثال على كيفية استخدام Fastlz. Decompressor المقابل هو 6unpack .

يدعم Fastlz أي برنامج التحويل البرمجي ANSI C/C90 المعتاد ، بما في ذلك المترجمة الشائعة مثل GCC و Clang و Visual Studio وحتى CC Tiny. يعمل Fastlz بشكل جيد على عدد من البنى (32 بت و 64 بت ، كبيرة إنديان وليتل إنديان) ، من Intel/AMD ، PowerPC ، System Z ، ARM ، MIPS ، و RISC-V.

يدير نظام التكامل المستمر مجموعة واسعة من الرحلات المستديرة لضغط الانضغاط على الأنظمة التالية:

لمزيد من التفاصيل ، تحقق من سجلات GitHub المقابلة لإنشاء سجلات.


AMD64	Linux	النوافذ	ماكوس
مجلس التعاون الخليجي
كلانج
tinycc
مقابل 2019
I686	Linux	النوافذ	ماكوس
مجلس التعاون الخليجي
كلانج
tinycc
مقابل 2019
I586	Linux	دوس
مجلس التعاون الخليجي
	Linux
PowerPC
مجلس التعاون الخليجي
PPC64 (LE)
مجلس التعاون الخليجي
مجلس التعاون الخليجي
S390x
مجلس التعاون الخليجي
Armhf
مجلس التعاون الخليجي
ARM64
مجلس التعاون الخليجي
MIPS (EL)
مجلس التعاون الخليجي
مجلس التعاون الخليجي
MIPS64 (EL)
مجلس التعاون الخليجي
مجلس التعاون الخليجي
RISCV
مجلس التعاون الخليجي
RISCV64
مجلس التعاون الخليجي

تنسيق كتلة

دعنا نفترض أن Fastlz يضغط مجموعة من البايتات ، تسمى الكتلة غير المضغوطة ، في مجموعة أخرى من البايتات ، تسمى الكتلة المضغوطة . لفهم ما سيتم تخزينه في الكتلة المضغوطة ، من التوضيح أن توضح مدى قيام Fastlz بإزالة الضغط على الكتلة لاسترداد الكتلة الأصلية غير المضغوطة.

أول 3 بت من الكتلة ، أي البتات الثلاثة الأكثر أهمية في البايت الأول ، هي علامة الكتلة . تحدد علامة الكتلة حاليًا مستوى الضغط المستخدم لإنتاج الكتلة المضغوطة.

علامة العلامة	مستوى الضغط
0	المستوى 1
1	المستوى 2

سيختلف محتوى الكتلة حسب مستوى الضغط.

تنسيق كتلة للمستوى 1

Fastlz المستوى 1 ينفذ خوارزمية ضغط LZ77 مع نافذة انزلاق 8 كيلو بايت وما يصل إلى 264 بايت من طول المباراة.

تتكون الكتلة المضغوطة من تعليمات واحدة أو أكثر. تبدأ كل تعليمات برمز OPCODE 1-بايت ، أو رمز OPCODE 2-بايت ، أو رمز OPCODE 3-BETE.

نوع التعليمات	Opcode [0]	رمز opcy [1]	Opcode [2]
تشغيل حرفي	`000` ، L₄-L₀	-	-
مباراة قصيرة	M₂-M₀ ، R₁₂-R₈	R₇-R₀	-
تطابق طويل	`111` ، R₁₂-R₈	م	R₇-R₀

لاحظ أن التعليمات الأولى في كتلة مضغوطة هي دائمًا تشغيل حرفي.

تعليمات التشغيل الحرفي

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

تحدد البتات 5 ذات أهمية أقل من opcode[0] ، L ، عدد الحرفيات التي تتبع الرمز البسيط. تشير قيمة 0 إلى تشغيل حرفي 1 بايت ، 1 تشير إلى تشغيل حرفي 2 بايت ، وهلم جرا. الحد الأدنى للتشغيل الحرفي هو 1 والحد الأقصى للتشغيل الحرفي هو 32.

نسخ إزالة الضغط ( L + 1 ) بايت من التشغيل الحرفي ، بدءًا من الأول مباشرة بعد الرمز البسيط.

مثال : إذا كانت الكتلة المضغوطة عبارة عن صفيف 4 بايت من [0x02, 0x41, 0x42, 0x43] ، فإن الرمز opcode هو 0x02 وهذا يعني تشغيل حرفي من 3 بايت. سيقوم Decompressor بعد ذلك بنسخ 3 بايت اللاحقة ، [0x41, 0x42, 0x43] ، إلى المخزن المؤقت للإخراج. يمثل المخزن المؤقت للإخراج الآن الكتلة غير المضغوطة (الأصلية) ، [0x41, 0x42, 0x43] .

تعليمات مطابقة قصيرة

تحدد 3 أجزاء من opcode[0] ، M ، طول المباراة . تشير قيمة 1 إلى مباراة 3 بايت ، 2 تشير إلى مباراة 4 بايت وهلم جرا. الحد الأدنى لطول المباراة هو 3 والطول القصوى هو 8.

يتم دمج البتات الخمسة ذات الأهمية الأقل من opcode[0] مع 8 بتات من opcode[1] ، R ، الإزاحة المرجعية . نظرًا لأن الإزاحة مشفرة في 13 بت ، فإن الحد الأدنى هو 0 والحد الأقصى هو 8191.

يسترجع رمز C التالي طول المطابقة وإزاحة المرجع:

 M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];

نسخ إزالة الضغط (M+2) ، بدءًا من الموقع الذي تم تعويضه بواسطة R في المخزن المؤقت للإخراج. لاحظ أن R هو مرجع خلفي ، أي أن قيمة 0 تتوافق مع البايت الأخير في المخزن المؤقت للإخراج ، 1 هي البايت الثاني إلى الأخير ، وما إلى ذلك.

مثال 1 : إذا كانت الكتلة المضغوطة هي صفيف 7 بايت من [0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02] ، فهناك تعليمين في هناك. التعليمات الأولى هي التشغيل الحرفي من 4 بايت (بسبب L = 3 ). وبالتالي ، فإن إزالة الضغط على 4 بايت إلى المخزن المؤقت للإخراج ، مما يؤدي إلى [0x41, 0x42, 0x43, 0x44] . التعليمات الثانية هي المباراة القصيرة لـ 3 بايت (من M = 1 ، IE 0x20 >> 5 ) وإزاحة 2. لذلك ، يعود الضاغط إلى 2 بايت من الموضع الأخير ، والنسخ 3 بايت ( [0x42, 0x43, 0x44] ) ، ويسددها إلى المخزن المؤقت للإخراج. يمثل المخزن المؤقت للإخراج الآن البيانات غير المضغوطة الكاملة ، [0x41, 0x42, 0x43, 0x44, 0x42, 0x43, 0x44] .

مثال 2 : إذا كانت الكتلة المضغوطة عبارة عن مجموعة 4 بايت من [0x00, 0x61, 0x40, 0x00] ، فهناك تعليمين هناك. التعليمات الأولى هي الجري الحرفي البالغ 1 بايت فقط ( L = 0 ). وهكذا ، يقوم إزالة الضغط بنسخ البايت ( 0x61 ) إلى المخزن المؤقت للإخراج. يصبح المخزن المؤقت للإخراج الآن [0x61] . التعليمات الثانية هي المباراة القصيرة لـ 4 بايت (من M = 2 ، IE 0x40 >> 5 ) وإزاحة 0. لذلك ، تبدأ نسخ الضغط 4 بايت باستخدام المرجع الخلفي لـ 0 (أي موضع 0x61 ). يمثل المخزن المؤقت للإخراج الآن البيانات غير المضغوطة الكاملة ، [0x61, 0x61, 0x61, 0x61, 0x61] .

تعليمات مطابقة طويلة

قيمة opcode[1] ، م ، تحدد طول المطابقة . تشير قيمة 0 إلى تطابق 9 بايت ، 1 تشير إلى مباراة 10 بايت وهلم جرا. الحد الأدنى لطول المباراة هو 9 والطول القصوى هو 264.

يتم دمج البتات 5 ذات أهمية أقل من opcode[0] مع 8 بتات من opcode[2] ، R ، الإزاحة المرجعية . نظرًا لأن الإزاحة مشفرة في 13 بت ، فإن الحد الأدنى هو 0 والحد الأقصى هو 8191.

يسترجع رمز C التالي طول المطابقة وإزاحة المرجع:

 M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];

نسخ إزالة الضغط (M+9) ، بدءًا من الموقع الذي تم تعويضه بواسطة R في المخزن المؤقت للإخراج. لاحظ أن R هو مرجع خلفي ، أي أن قيمة 0 تتوافق مع البايت الأخير في المخزن المؤقت للإخراج ، 1 هو للبايت الثاني إلى الأخير ، وهكذا دواليك.

مثال : إذا كانت الكتلة المضغوطة عبارة عن مجموعة 4 بايت من [0x01, 0x44, 0x45, 0xE0, 0x01, 0x01] ، فهناك تعليمين هناك. التعليمات الأولى هي التشغيل الحرفي بطول 2 (بسبب L = 1 ). وهكذا ، يقوم Decompressor بنسخ التشغيل الحرفي 2 بايت ( [0x44, 0x45] ) إلى المخزن المؤقت للإخراج. التعليمات الثانية هي المباراة الطويلة مع طول المطابقة 10 (من M = 1 ) وإزاحة 1. لذلك ، فإن إزالة الضغط على 10 بايت تبدأ باستخدام مرجع الخلفي من 1 (أي موضع 0x44 ). يمثل المخزن المؤقت للإخراج الآن البيانات غير المضغوطة الكاملة ، [0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45] .

تنفيذ مرجع إلغاء الضغط

تنفذ وظيفة C-40-Liner C. لاحظ أنه يهدف إلى أن تكون تعليمية ، على سبيل المثال لا يتم تنفيذ الفحص الملزم ، وبالتالي فهو غير آمن على الإطلاق للإنتاج.

 void fastlz_level1_decompress ( const uint8_t * input , int length , uint8_t * output ) {
  int src = 0 ;
  int dest = 0 ;
  while ( src < length ) {
    int type = input [ src ] >> 5 ;
    if ( type == 0 ) {
      /* literal run */
      int run = 1 + input [ src ];
      src = src + 1 ;
      while ( run > 0 ) {
        output [ dest ] = input [ src ];
        src = src + 1 ;
        dest = dest + 1 ;
        run = run - 1 ;
      }
    } else if ( type < 7 ) {
      /* short match */
      int ofs = 256 * ( input [ src ] & 31 ) + input [ src + 1 ];
      int len = 2 + ( input [ src ] >> 5 );
      src = src + 2 ;
      int ref = dest - ofs - 1 ;
      while ( len > 0 ) {
        output [ dest ] = output [ ref ];
        ref = ref + 1 ;
        dest = dest + 1 ;
        len = len - 1 ;
      }
    } else {
      /* long match */
      int ofs = 256 * ( input [ src ] & 31 ) + input [ src + 2 ];
      int len = 9 + input [ src + 1 ];
      src = src + 3 ;
      int ref = dest - ofs - 1 ;
      while ( len > 0 ) {
        output [ dest ] = output [ ref ];
        ref = ref + 1 ;
        dest = dest + 1 ;
        len = len - 1 ;
      }
    }
  }
}