streamvbyte simdgo
v0.4.0
هذا مستودع يحتوي على منفذ دفق vbyte للذهاب. والجدير بالذكر أن هذا الريبو يأخذ المزيد من العناية بالاستفادة من تقنيات SIMD لتحقيق أداء أفضل. حاليًا ، هناك دعم لبنية X86_64 التي تحتوي على تعليمات أجهزة AVX و AVX2. في الحالات التي لا يتوفر فيها ذلك ، أو على بنيات غير x86_64 ، يوجد تطبيق قياسي محمول. نقوم أيضًا بإجراء فحص وقت التشغيل للتأكد من توفر ISA اللازم ، وإذا لم يكن متاحًا لنهج العددية.
هناك العديد من التطبيقات الحالية:
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
MemCopy8Uint32-12 463986302 2.608 ns/op 12269.03 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/decode
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
Get8uint32Fast-12 377839186 3.170 ns/op 10095.99 MB/s
Get8uint32DeltaFast-12 298522095 4.455 ns/op 7183.20 MB/s
Get8uint32Scalar-12 63384603 19.28 ns/op 1659.36 MB/s
Get8uint32DeltaScalar-12 58705828 20.04 ns/op 1596.46 MB/s
Get8uint32Varint-12 27369775 43.77 ns/op 731.10 MB/s
Get8uint32DeltaVarint-12 20924770 57.30 ns/op 558.46 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/encode
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
Put8uint32Fast-12 297620898 3.864 ns/op 8281.18 MB/s
Put8uint32DeltaFast-12 276545827 4.350 ns/op 7356.59 MB/s
Put8uint32Scalar-12 41200776 28.59 ns/op 1119.30 MB/s
Put8uint32DeltaScalar-12 37773458 30.65 ns/op 1044.11 MB/s
Put8uint32Varint-12 58668867 17.20 ns/op 1860.67 MB/s
Put8uint32DeltaVarint-12 61446153 22.88 ns/op 1398.80 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/stream/reader
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
ReadAllFast/Count_1e0-12 99354789 12.24 ns/op 326.80 MB/s
ReadAllFast/Count_1e1-12 28076071 42.81 ns/op 934.43 MB/s
ReadAllFast/Count_1e2-12 11041639 107.2 ns/op 3730.16 MB/s
ReadAllFast/Count_1e3-12 1645387 729.9 ns/op 5480.00 MB/s
ReadAllFast/Count_1e4-12 170894 7034 ns/op 5686.52 MB/s
ReadAllFast/Count_1e5-12 16848 70969 ns/op 5636.29 MB/s
ReadAllFast/Count_1e6-12 1513 728516 ns/op 5490.62 MB/s
ReadAllFast/Count_1e7-12 152 7835111 ns/op 5105.22 MB/s
ReadAllDeltaFast/Count_1e0-12 92727970 13.10 ns/op 305.44 MB/s
ReadAllDeltaFast/Count_1e1-12 26164140 45.89 ns/op 871.61 MB/s
ReadAllDeltaFast/Count_1e2-12 9458992 128.5 ns/op 3113.55 MB/s
ReadAllDeltaFast/Count_1e3-12 1277408 934.4 ns/op 4280.69 MB/s
ReadAllDeltaFast/Count_1e4-12 144405 8318 ns/op 4808.88 MB/s
ReadAllDeltaFast/Count_1e5-12 14444 83151 ns/op 4810.55 MB/s
ReadAllDeltaFast/Count_1e6-12 1426 846305 ns/op 4726.43 MB/s
ReadAllDeltaFast/Count_1e7-12 127 9337355 ns/op 4283.87 MB/s
ReadAllScalar/Count_1e0-12 122650209 9.770 ns/op 409.43 MB/s
ReadAllScalar/Count_1e1-12 38012136 31.63 ns/op 1264.64 MB/s
ReadAllScalar/Count_1e2-12 4999376 241.6 ns/op 1655.30 MB/s
ReadAllScalar/Count_1e3-12 500337 2459 ns/op 1626.38 MB/s
ReadAllScalar/Count_1e4-12 50247 24034 ns/op 1664.34 MB/s
ReadAllScalar/Count_1e5-12 5032 238354 ns/op 1678.17 MB/s
ReadAllScalar/Count_1e6-12 499 2405669 ns/op 1662.74 MB/s
ReadAllScalar/Count_1e7-12 46 24533207 ns/op 1630.44 MB/s
ReadAllDeltaScalar/Count_1e0-12 100000000 10.32 ns/op 387.49 MB/s
ReadAllDeltaScalar/Count_1e1-12 36915704 32.52 ns/op 1230.08 MB/s
ReadAllDeltaScalar/Count_1e2-12 4818140 249.8 ns/op 1601.58 MB/s
ReadAllDeltaScalar/Count_1e3-12 512492 2374 ns/op 1685.20 MB/s
ReadAllDeltaScalar/Count_1e4-12 51004 23639 ns/op 1692.11 MB/s
ReadAllDeltaScalar/Count_1e5-12 3568 333168 ns/op 1200.60 MB/s
ReadAllDeltaScalar/Count_1e6-12 520 2304864 ns/op 1735.46 MB/s
ReadAllDeltaScalar/Count_1e7-12 48 24810555 ns/op 1612.22 MB/s
ReadAllVarint/Count_1e0-12 121348074 9.967 ns/op 401.34 MB/s
ReadAllVarint/Count_1e1-12 21056739 57.34 ns/op 697.64 MB/s
ReadAllVarint/Count_1e2-12 2025081 589.0 ns/op 679.15 MB/s
ReadAllVarint/Count_1e3-12 205881 5851 ns/op 683.69 MB/s
ReadAllVarint/Count_1e4-12 20906 57446 ns/op 696.31 MB/s
ReadAllVarint/Count_1e5-12 2037 580620 ns/op 688.92 MB/s
ReadAllVarint/Count_1e6-12 208 5755083 ns/op 695.04 MB/s
ReadAllVarint/Count_1e7-12 20 57872736 ns/op 691.17 MB/s
ReadAllDeltaVarint/Count_1e0-12 139763250 8.318 ns/op 480.87 MB/s
ReadAllDeltaVarint/Count_1e1-12 19199100 62.49 ns/op 640.11 MB/s
ReadAllDeltaVarint/Count_1e2-12 2149660 556.6 ns/op 718.65 MB/s
ReadAllDeltaVarint/Count_1e3-12 207122 5810 ns/op 688.41 MB/s
ReadAllDeltaVarint/Count_1e4-12 22680 53200 ns/op 751.88 MB/s
ReadAllDeltaVarint/Count_1e5-12 2145 500177 ns/op 799.72 MB/s
ReadAllDeltaVarint/Count_1e6-12 228 5262741 ns/op 760.06 MB/s
ReadAllDeltaVarint/Count_1e7-12 27 42000722 ns/op 952.36 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/stream/writer
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
WriteAllFast/Count_1e0-12 54152408 22.05 ns/op 181.36 MB/s
WriteAllFast/Count_1e1-12 27681948 43.17 ns/op 926.49 MB/s
WriteAllFast/Count_1e2-12 7136480 167.0 ns/op 2395.79 MB/s
WriteAllFast/Count_1e3-12 928952 1273 ns/op 3141.14 MB/s
WriteAllFast/Count_1e4-12 96117 12012 ns/op 3329.93 MB/s
WriteAllFast/Count_1e5-12 9718 114260 ns/op 3500.80 MB/s
WriteAllFast/Count_1e6-12 879 1242927 ns/op 3218.21 MB/s
WriteAllFast/Count_1e7-12 100 10368754 ns/op 3857.74 MB/s
WriteAllDeltaFast/Count_1e0-12 50489378 23.38 ns/op 171.06 MB/s
WriteAllDeltaFast/Count_1e1-12 26866423 45.03 ns/op 888.33 MB/s
WriteAllDeltaFast/Count_1e2-12 6695125 175.8 ns/op 2275.37 MB/s
WriteAllDeltaFast/Count_1e3-12 899895 1391 ns/op 2875.71 MB/s
WriteAllDeltaFast/Count_1e4-12 90394 12958 ns/op 3086.82 MB/s
WriteAllDeltaFast/Count_1e5-12 10000 122319 ns/op 3270.13 MB/s
WriteAllDeltaFast/Count_1e6-12 945 1249546 ns/op 3201.16 MB/s
WriteAllDeltaFast/Count_1e7-12 100 11461852 ns/op 3489.84 MB/s
WriteAllScalar/Count_1e0-12 56106489 21.72 ns/op 184.18 MB/s
WriteAllScalar/Count_1e1-12 18309972 65.09 ns/op 614.51 MB/s
WriteAllScalar/Count_1e2-12 2776918 433.5 ns/op 922.63 MB/s
WriteAllScalar/Count_1e3-12 289309 4209 ns/op 950.38 MB/s
WriteAllScalar/Count_1e4-12 29497 40884 ns/op 978.38 MB/s
WriteAllScalar/Count_1e5-12 3027 399959 ns/op 1000.10 MB/s
WriteAllScalar/Count_1e6-12 296 4010161 ns/op 997.47 MB/s
WriteAllScalar/Count_1e7-12 28 38753790 ns/op 1032.16 MB/s
WriteAllDeltaScalar/Count_1e0-12 54981757 21.90 ns/op 182.65 MB/s
WriteAllDeltaScalar/Count_1e1-12 17823349 67.10 ns/op 596.14 MB/s
WriteAllDeltaScalar/Count_1e2-12 2711672 442.4 ns/op 904.09 MB/s
WriteAllDeltaScalar/Count_1e3-12 292664 4130 ns/op 968.62 MB/s
WriteAllDeltaScalar/Count_1e4-12 29340 41014 ns/op 975.28 MB/s
WriteAllDeltaScalar/Count_1e5-12 2289 516113 ns/op 775.02 MB/s
WriteAllDeltaScalar/Count_1e6-12 302 3930860 ns/op 1017.59 MB/s
WriteAllDeltaScalar/Count_1e7-12 30 41357670 ns/op 967.17 MB/s
WriteAllVarint/Count_1e0-12 208214545 5.720 ns/op 699.32 MB/s
WriteAllVarint/Count_1e1-12 43083270 28.02 ns/op 1427.34 MB/s
WriteAllVarint/Count_1e2-12 4972045 242.8 ns/op 1647.67 MB/s
WriteAllVarint/Count_1e3-12 499011 2409 ns/op 1660.60 MB/s
WriteAllVarint/Count_1e4-12 51022 23590 ns/op 1695.67 MB/s
WriteAllVarint/Count_1e5-12 5216 231741 ns/op 1726.07 MB/s
WriteAllVarint/Count_1e6-12 518 2305364 ns/op 1735.08 MB/s
WriteAllVarint/Count_1e7-12 50 24905825 ns/op 1606.05 MB/s
WriteAllDeltaVarint/Count_1e0-12 175269966 6.792 ns/op 588.93 MB/s
WriteAllDeltaVarint/Count_1e1-12 51799438 23.38 ns/op 1710.63 MB/s
WriteAllDeltaVarint/Count_1e2-12 5417458 221.3 ns/op 1807.60 MB/s
WriteAllDeltaVarint/Count_1e3-12 539414 2243 ns/op 1783.48 MB/s
WriteAllDeltaVarint/Count_1e4-12 52717 22753 ns/op 1757.99 MB/s
WriteAllDeltaVarint/Count_1e5-12 5716 210456 ns/op 1900.63 MB/s
WriteAllDeltaVarint/Count_1e6-12 495 2453672 ns/op 1630.21 MB/s
WriteAllDeltaVarint/Count_1e7-12 70 17491186 ns/op 2286.87 MB/s
ملاحظة على المعايير: يتم إنشاء مجموعة من UINT32 العشوائية ثم ترميزها/فك تشفيرها مرارًا وتكرارًا. تم إجراء محاولة لضمان أن بعض هذه المعايير تعكس مقاييس الأداء في العالم الحقيقي الأكثر احتمالا.
يستخدم Stream Vbyte نفس التنسيق الأساسي مثل نهج Varint مجموعة Google. Lemire et al. أردت معرفة ما إذا كانت هناك طريقة لتحسين الأداء أكثر وقدم تطورًا ذكيًا لتمكين أداء أفضل عبر تقنيات SIMD. الهدف الأساسي لتنسيق مجموعة Varint هو أن تكون قادرًا على تحقيق خصائص ضغط مماثلة كتنسيق Vbyte للأعداد الصحيحة وأيضًا أن تكون قادرًا على تحميلها ومعالجتها بسرعة.
إن البصيرة التي تدعم ترميز VBYTE هي أن تلاحظ أنك في كثير من الأحيان لا تحتاج إلى 32 بت لترميز عدد صحيح 32 بت. خذ على سبيل المثال عدد صحيح غير موقّع أقل من 2^8 (256). سيكون لهذا عدد صحيح أجزاء محددة في أدنى بايت من عدد صحيح 32 بت ، في حين أن 3 بايت المتبقية ستكون ببساطة الأصفار.
111 in binary:
00000000 00000000 00000000 01101111
إن النهج الذي يمكنك اتباعه لضغط هذا العدد صحيح هو تشفير عدد صحيح باستخدام عدد متغير من البايتات. على سبيل المثال ، يمكنك استخدام أقل 7 بتات لتخزين البيانات ، أي بتات من عدد صحيح أصلي ، ثم استخدام MSB كبت استمرار. إذا كان Bit MSB قيد التشغيل ، فإن IE هو 1 ، فمن الضروري وجود المزيد من البايتات لفك تشفير هذا عدد صحيح معين. فيما يلي مثال قد تحتاج فيه إلى 2 بايت لتخزين الرقم 1234.
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
إذا كنت ترغب في فك تشفير هذا عدد صحيح ، فأنت ببساطة تقوم ببناء الرقم بشكل متكرر. أي أن أنت أو آخر 7 بتات من كل بايت تحولت إلى الطول المناسب إلى عدد صحيح 32 بت حتى تجد بايت لا يحتوي على مجموعة بت استمرار. لاحظ أن هذا يعمل نفس الشيء بالنسبة لأرقام 64 بت.
تكمن المشكلة في هذا النهج في أنه يمكن أن يقدم الكثير من السلطات الخاطئة للفروع أثناء الترميز/فك التشفير. خلال مرحلة فك التشفير ، لا تعرف في وقت مبكر عدد البايتات التي تم استخدامها لتشفير عدد صحيح تقوم معالجته حاليًا ، وبالتالي تحتاج إلى التكرار حتى تجد بايت دون استمرار. إذا كان لديك أعداد صحيحة غير موحدة ، أي الأعداد الصحيحة التي تتطلب أعدادًا عشوائية من البايتات للتشفير بالنسبة إلى بعضها البعض ، فإن هذا يمكن أن يشكل تحديًا لتنبؤ فرع المعالج. يمكن أن تسبب هذه السلطات الخاطئة تباطؤًا كبيرًا في خطوط أنابيب المعالج ، وبالتالي ولدت تنسيق مجموعة Varint.
يفترض تنسيق مجموعة Varint (varint-GB) أن كل ما تأمل في تحقيقه ، يمكنك القيام به مع أعداد صحيحة 32 بت. يقدم مفهوم بايت التحكم الذي هو ببساطة بايت يخزن الأطوال المشفرة لمجموعة من 4 أعداد صحيحة 32 بت ، وبالتالي مجموعة varint. تتطلب الأعداد الصحيحة 32 بت فقط ما يصل إلى 4 بايت للتشفير بشكل صحيح. هذا يعني أنه يمكنك تمثيل أطوالها مع 2 بتات باستخدام طول فهرس صفر IE 0 و 1 و 2 و 3 لتمثيل الأعداد الصحيحة التي تتطلب 1 و 2 و 3 و 4 بايت للتشفير ، على التوالي.
00000000 00000000 00000000 01101111 = 111
00000000 00000000 00000100 11010010 = 1234
00000000 00001100 00001010 10000011 = 789123
01000000 00000000 00000000 00000000 = 1073741824
Num Len 2-bit control
----------------------------------
111 1 0b00
1234 2 0b01
789123 3 0b10
1073741824 4 0b11
Final Control byte
0b11100100
Encoded data (little endian right-to-left bottom-to-top)
0b01000000 0b00000000 0b00000000 0b00000000 0b00001100
0b00001010 0b10000011 0b00000100 0b11010010 0b01101111
يمكنك بعد ذلك بادئة كل مجموعة من 4 أعداد صحيحة 32 بت مشفرة مع بايت تحكمها ثم استخدامها أثناء فك التشفير. الجانب السلبي الواضح هو أنك تدفع تكلفة تخزين بايت واحد لكل عام 4 أعداد صحيحة تريد تشفيرها. ل 2^20 أعداد صحيحة مشفرة ، وهذا هو 256 كيلو بايت إضافية من مساحة إضافية: هامشية تماما. ومع ذلك ، فإن الاتجاه الصعودي العظيم هو أنك قمت الآن بإزالة جميع الفروع تقريبًا من مرحلة فك التشفير. أنت تعرف بالضبط عدد بايت البيانات التي تحتاج إلى قراءتها من المخزن المؤقت لرقم معين ومن ثم يمكنك استخدام فك التشفير بدون فرع.
package foo
import (
"encoding/binary"
)
func decodeOne ( input [] byte , size uint8 ) uint32 {
buf := make ([] byte , 4 )
copy ( buf , input [: size ])
// func (littleEndian) Uint32(b []byte) uint32 {
// _ = b[3]
// return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
// }
return binary . LittleEndian . Uint32 ( buf )
}
func main () {
ctrl := uint8 ( 0b11_10_01_00 )
data := [] byte {
0b01101111 , 0b11010010 , 0b00000100 ,
0b10000011 , 0b00001010 , 0b00001100 ,
0b00000000 , 0b00000000 , 0b00000000 ,
0b01000000 ,
}
len0 := ( ctrl & 3 ) + 1 // 1
len1 := ( ctrl >> 2 & 3 ) + 1 // 2
len2 := ( ctrl >> 4 & 3 ) + 1 // 3
len3 := ( ctrl >> 6 & 3 ) + 1 // 4
_ = decodeOne ( data , len0 ) // 111
_ = decodeOne ( data [ len0 :], len1 ) // 1234
_ = decodeOne ( data [ len0 + len1 :], len2 ) // 789_123
_ = decodeOne ( data [ len0 + len1 + len2 :], len3 ) // 1_073_741_824
}لسوء الحظ ، أثبت تسريع فك ترميز تنسيق Varint-GB مع تقنيات SIMD فقط. المقتطف أدناه من الورقة يحدد السبب.
لفهم سبب صعوبة تسريع فك تشفير البيانات المضغوطة بتنسيق Varint-GB مقارنة بتنسيق Varint-G8IU ، ضع في اعتبارك أنه لا يمكننا فك التشفير بشكل أسرع مما يمكننا الوصول إلى بايت التحكم. في Varint-G8IU ، توجد بايت التحكم دائمًا في مكان مريح تسعة بايتات مضغوطة. وبالتالي ، بينما تتم معالجة بايت التحكم ، أو حتى قبل ، يمكن للمعالج superscalar لدينا تحميل وبدء معالجة بايت التحكم القادم ، حيث يمكن التنبؤ بمواقعها. يمكن إعادة ترتيب التعليمات اعتمادًا على وحدات التحكم هذه بواسطة المعالج للحصول على أفضل أداء. ومع ذلك ، في تنسيق Varint-GB ، هناك اعتماد قوي على البيانات: يعتمد موقع بايت التحكم التالي على بايت التحكم الحالي. هذا يزيد من خطر أن يظل المعالج غير مستغلة ، وتأخر بسبب الكمون بين إصدار الحمل لبايت التحكم التالي وانتظار أن يكون جاهزًا.
بالإضافة إلى ذلك ، يثبتون أن فك تشفير 4 أعداد صحيحة في وقت واحد باستخدام سجلات 128 بت أسرع من محاولة فك تشفير عدد متغير من الأعداد الصحيحة التي تتناسب مع سجل 8 بايت ، أي نهج Varint-G8IU.
Lemire et al. ابتكرت خوارزمية SIMD الرائعة لتوليد بايتات تحكم في وقت واحد لمجموعة من 8 أعداد صحيحة. أفضل طريقة لفهم هذه الخوارزمية هي فهم كيفية عملها على عدد صحيح واحد ثم تفترض أنها تعمل في شكل متجه (تفعل). للمضي قدمًا ، سنستخدم دفق البتات التحكم لتمثيل بايت التحكم التي نبنيها.
00000000 00000000 00000100 11010010 // 1234
دعنا نأخذ أحد الأعداد الصحيحة السابقة التي كنا ننظر إليها ، 1234 ، ونمر بمثال على كيفية إنشاء التحكم 2 بت باستخدام تقنيات SIMD. الهدف من ذلك هو أن تكون قادرًا على ، لأي عدد صحيح 32 بت ، إنشاء قيمة طول مفهرسة 2 بت صفر. على سبيل المثال ، إذا كان لديك عدد صحيح يتطلب تشفير 2 بايت ، فنحن نريد أن تنشئ الخوارزمية 0b01 .
00000000 00000000 00000100 11010010 // 1234
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1234, 0x0101)
00000000 00000000 00000001 00000001
تستخدم الخوارزمية أولاً قناعًا حيث كل بايت يساوي 1. إذا قمت بإجراء عملية لكل بايت على عدد صحيح وقناع 1 ، فستكون النتيجة 1 في كل بايت كان لها قيمة في عدد صحيح أصلي.
00000000 00000000 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000000 11111111
يمكنك الآن إجراء عملية تشبع غير موقعة من 16 بت إلى 8 بت. من الناحية العملية ، هذا يعني أنك تأخذ كل قيمة 16 بت ومحاولة دفع ذلك إلى 8 بت. إذا كان عدد صحيح 16 بت أكبر من أكبر عدد صحيح غير موقّع 8 بتات ، فإن الحزمة تشبع إلى أكبر قيمة 8 بت غير موقعة.
لماذا يتم تنفيذ ذلك سيصبح أكثر وضوحًا في الخطوات اللاحقة ، على مستوى عالٍ ، لكل عدد صحيح تريد تشفيره ، تريد أن يكون MSB من بايتتين متتاليتين في دفق البتات التحكم يمثل التحكم الأخير 2 بت. على سبيل المثال ، إذا كان لديك عدد صحيح من 3 بايت ، فأنت تريد أن يكون MSB من بايتتين متتاليتين 1 و 0 ، بهذا الترتيب. السبب في أنك تريد هذا هو أن هناك تعليمات حزمة المتجهات التي تأخذ MSB من كل بايت في تيار بتات التحكم ويحزمها في أدنى بايت. وبالتالي ، فإن هذا يمثل القيمة 0b10 في البايت النهائي لهذا عدد صحيح 3 بايت ، وهو ما نريده.
إن إجراء حزمة التشبع غير الموقعة من 16 بت إلى 8 بت لها تأثير على أنه يمكنك استخدام سلوك التشبع لتشغيل MSB بشكل مشروط من هذه البايتات اعتمادًا على البايتات التي لها قيم في عدد صحيح 32 بت الأصلي.
00000000 00000000 00000000 11111111 // control bits stream
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000000 11111111
ثم نأخذ قناع 1 الذي استخدمناه من قبل ونؤدي عملية موقعة 16 بت . السبب في ذلك أكثر وضوحًا إذا نظرت إلى مثال باستخدام عدد صحيح 3 بايت.
00000000 00001100 00001010 10000011 // 789123
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(789123, 0x0101)
00000000 00000001 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000001 11111111
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000001 00000001
العملية الموقعة 16 بت دقيقة لها ثلاثة آثار مهمة.
أولاً ، بالنسبة للأعداد الصحيحة 3 بايت ، يكون لها تأثير إيقاف تشغيل MSB لأدنى بايت. هذا ضروري لأن عدد صحيح 3 بايت يجب أن يكون له عنصر تحكم 2 بت هو 0b10 وبدون هذه الخطوة باستخدام عملية حزمة MSB سيؤدي إلى تحكم 2 بت يشبه 0b_1 ، حيث يكون أقل بت. من الواضح أن هذا خطأ ، لأن الأعداد الصحيحة التي تتطلب فقط 2 أو 4 بايت للتشفير يجب أن يكون لها هذا البكت المنخفض ، أي 1 أو 3 كطول مفهرس صفر.
ثانياً ، بالنسبة للأعداد الصحيحة ذات 4 بايت ، فإن الجانب الموقّع له تأثير ترك كل من MSBs من 2 بايت. عند استخدام عملية MSB Pack لاحقًا ، سيؤدي ذلك إلى قيمة تحكم 2 بت من 0b11 ، وهو ما نريده.
ثالثًا ، لمدة 1 و 2 أعداد صحيحة بايت ، ليس لها أي تأثير. يعد هذا أمرًا رائعًا بالنسبة للقيم 2 بايت نظرًا لأن MSB سيبقى في وضع واحد ، ولن يكون لدى قيم البايت 1 أي MSB على أي حال ، لذلك فهو NOOP فعليًا في كلا السيناريوهين.
00000000 00000000 00000000 11111111 // control bits stream (original 1234)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 01111111 11111111
بعد ذلك ، نأخذ قناعًا مع القيمة 0x7F00 ونؤدي إضافة تشبع غير موقعة إلى دفق بتات التحكم. في حالة عدد صحيح 1234 ليس له تأثير حقيقي. نحافظ على MSB في أدنى بايت. ومع ذلك ، ستلاحظ أن البايت الوحيد الذي يحتوي على MSB عليه هو الأخير ، لذا فإن إجراء عملية حزمة MSB سيؤدي إلى قيمة 0b0001 ، وهو ما نريده. مثال على هذه الخطوة على عدد صحيح 789123 قد يرسم صورة أوضح.
00000000 00000000 00000001 00000001 // control bits stream (789123)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 00000001
ستلاحظ هنا أن إضافة 0x01 مع 0x7F في البايت العلوي يؤدي إلى MSB للبايت العلوي الناتج. لا يزال MSB في البايت السفلي خارجًا ، وسيتم حل عملية حزمة MSB الآن إلى 0b0010 ، وهو ما نريده. يعد سلوك التشبع غير الموقّع مهمًا حقًا للأرقام 4 بايت التي تحتوي فقط على أجزاء في البايت الأكثر أهمية. مثال أدناه:
01000000 00000000 00000000 00000000 // 1073741824
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1073741824, 0x0101)
00000001 00000000 00000000 00000000
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 11111111 00000000
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 11111111 00000000
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 11111111
لاحظ هنا أنه لأن البايت العلوي فقط كان له قيمة فيه ، فإن أدنى بايت في تيار بتات التحكم يبقى صفرًا طوال مدة الخوارزمية. هذا يمثل مشكلة ، لأنه بالنسبة لقيمة 4 بايت ، نريد أن يؤدي التحكم 2 بت إلى قيمة 0b11 . إن إجراء إضافة مشبعة غير موقعة 16 بت على تشغيل جميع البتات في البايت السفلي ، وبالتالي نحصل على نتيجة مع MSB في البايت السفلي.
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
يتم تنفيذ قناع Byte Byte النهائي على تيار بتات التحكم ، ولدينا الآن النتيجة التي أردناها. الآن بعد أن رأيت أن هذا يعمل من أجل عدد صحيح واحد ، فأنت تعرف كيف يمكن أن يعمل لمدة 8 أعداد صحيحة في وقت واحد ، نظرًا لأننا نستخدم تعليمات المتجهات التي تعمل في سجل 128 بت.
المشكلة التالية التي يجب حلها هي كيفية أخذ مجموعة من 4 أعداد صحيحة ، وضغطها عن طريق إزالة البايتات الخارجية/غير المستخدمة بحيث تكون كل ما تبقى معه هو دفق من بايت البيانات بمعلومات حقيقية. لنأخذ رقمين من أمثلةنا أعلاه.
789123 1234
00000000 00001100 00001010 10000011 | 00000000 00000000 00000100 11010010
-------------------------------------------------------------------------
00001100 00001010 10000011 00000100 11010010 // packed
هنا ، يمكننا استخدام عملية خلط ورق اللعب. إعادة ترتيب عمليات خلط المتجول المتجه إلى البايتات في سجل إدخال وفقًا لبعض القناع المقدم في سجل الوجهة. يخزن كل موضع في القناع إزاحة في دفق متجه المصدر الذي يمثل بايت البيانات الذي يجب أن يدخل هذا الموضع.
input [1234, 789123] (little endian R-to-L)
00000000 00001100 00001010 10000011 00000000 00000000 00000100 11010010
| | | | |
| | |____________________ | |
| |_____________________ | | |
|____________________ | | | |
v v v v v
0xff 0xff 0xff 0x06 0x05 0x04 0x01 0x00 // mask in hex
-----------------------------------------------------------------------
00000000 00000000 00000000 00001100 00001010 10000011 00000100 11010010 // packed
نحتفظ بجدول بحث مسبقًا يحتوي على رسم خرائط من بايت التحكم إلى القناع اللازم وبدذا بعد أن نبني بايت التحكم أعلاه. بالإضافة إلى ذلك ، نحتفظ بجدول بحث لرسم خرائط من بايت التحكم إلى الطول المشفر الكلي. يتيح لنا ذلك معرفة المبلغ الذي يجب زيادة مؤشر الإخراج والكتابة فوقها ، على سبيل المثال ، بايت 3 العليا الزائدة في مثال خلط الخلط أعلاه.
التفريغ أثناء فك التشفير هو نفسه ما سبق ، ولكن في الاتجاه المعاكس. نحتاج إلى الانتقال من تنسيق معبأة إلى تنسيق ذاكرة غير معبأة. نحافظ على جداول البحث للحفاظ على رسم خرائط من بايت التحكم إلى قناع خلط الخلط العكسي ، ثم إجراء عملية خلط خلط الشكل لإخراج مجموعة uint32 .
دفق vbyte: ضغط عدد صحيح موجه بايت أسرع
