يجب تشفير الأحرف إلى وحدات بت بطريقة ما. تم ترميز معظم الأوتار على الإنترنت ، بما في ذلك هذا المنشور على Habré ، في UTF-8. يمثل تنسيق UTF-8 "أحرفًا" بحجم واحد أو اثنين أو ثلاثة أو أربعة بايت. هذا تعميم لمعيار ASCII ، والذي يستخدم بايت واحد فقط لكل حرف. وهذا يعني أن سلسلة ASCII هي أيضًا سلسلة UTF-8.
إنه في الواقع أكثر تعقيدًا بعض الشيء لأنه من الناحية الفنية يصف UTF-8 نقاط الكود. يمكن أن تتكون الشخصية المرئية مثل الرموز التعبيرية من نقاط رمز متعددة ... لكن معظم المبرمجين لا يحتاجون إلى هذه الصياغة المبتذلة.
هناك معايير أخرى كذلك. تعتمد بعض لغات البرمجة القديمة مثل C # و Java على UTF-16. يستخدم اثنين أو أربعة بايت لكل حرف. بدت فكرة جيدة في ذلك الوقت ، لكن الإجماع الآن يتجه نحو استخدام UTF-8 في أي وقت وفي أي مكان.
معظم الترميزات لها قيود قابلة للتنفيذ. بمعنى آخر ، ليس كل تسلسل بت عشوائي يمكن أن ينتقل إلى UTF-8. وبالتالي ، تحتاج إلى التحقق من صحة السلاسل - تحقق من أنها بالفعل UTF-8.
ما الدي يهم؟ عظيم. على سبيل المثال ، يحتوي خادم الويب الخاص بشركة Microsoft على مثل هذه الثغرة الأمنية: فهو يقبل URI الذي يبدو أنه صالح وآمن ، ولكن بعد أن يتم تفسيره بواسطة الخادم ، فإنه يمنح المهاجم وصولاً عن بُعد إلى القرص. حتى لو تركت مخاوف الأمان جانباً ، فمن شبه المؤكد أنك لا تريد تخزين صفوف غير صالحة في قاعدة البيانات الخاصة بك.
وبالتالي ، فإن لغات البرمجة وخوادم الويب والمتصفحات ومحركات قواعد البيانات تتحقق باستمرار من صحة UTF-8.
إذا كانت السلاسل الخاصة بك في الغالب مجرد ASCII ، فستكون عمليات التحقق سريعة جدًا ولا يمثل فحص UTF-8 مشكلة. لقد ولت الأيام التي تم فيها تشفير معظم السلاسل ASCII. نحن نعيش في عالم من الرموز التعبيرية والعديد من الأبجديات الوطنية.
في عام 2018 ، سألت نفسي:ما مدى سرعة التحقق من صحة سلاسل UTF-8 ؟ في ذلك الوقت ، وجدت خيار التحقق من الصحة مع عدة دورات وحدة المعالجة المركزية لكل رمز. يمكن للمرء أن يهدأ من هذا ، لكن هذه الإجابة لم ترضيني.
استغرق العمل سنوات ، ولكن يبدو أننا حصلنا الآن على نسخة قريبة من المثالية. الخوارزمية الجديدة هي ترتيب من حيث الحجم أسرع من خيارات البحث السريع الأخرى. لقد قمنا بإعداد مستند تقني: "التحقق من صحة UTF-8 بأقل من تعليمات واحدة لكل بايت" (سيتم نشره في Software: Practice and Experience ) ونشرنا أيضًا أداة قياس الأداء .
تم شرح كل التفاصيل في مقال علمي ، لذلك لن ندخل في التفاصيل هنا ، ولكن فقط سننظر في الجوهر باختصار. يتم إجراء الجزء الرئيسي من التحقق من صحة UTF-8 من خلال البحث عن أزواج من البايت المتتالية. بعد فحص جميع أزواج البايت وتحديد أي انتهاكات محتملة يمكن العثور عليها من هذه المعلومات ، يتبقى القليل نسبيًا للقيام به.
تحتوي جميع المعالجات على تعليمات SIMD سريعة. أنها تعمل مع سجلات واسعة (128 بت ، 256 بت ، إلخ). تحتوي معظم المجموعات على تعليمات "بحث متجه" تأخذ ، على سبيل المثال ، قيم 16 بايت (تتراوح من 0 إلى 16) وتبحث عنها في جدول 16 بايت. في معالجات Intel و AMD ، يتوافق هذا الوصف مع التعليمات
pshufb... تسمى القيمة بين 0 و 16 أحيانًا nibble وتمتد إلى 4 بتات. يتكون البايت من اثنين من nibble (منخفض وعالي).
في خوارزمية البحث الخاصة بنا ، يتم استدعاء تعليمات البحث المتجه ثلاث مرات: مرة للقضم المنخفض ، ومرة للقضمة العالية ، ومرة للقضم العالي للبايت التالي. لدينا ثلاثة جداول بحث متطابقة 16 بايت. إذا تم تحديده بشكل صحيح ، فستجد أي خطأ AND في عمليات البحث الثلاثة.
راجع المقالة العلمية للحصول على مزيد من التفاصيل ، ولكن في النهاية تم التحقق من صحة UTF-8 شبه الكامل باستخدام خمسة أسطر فقط من كود C ++ السريع دون أي فروع ... وتتحقق هذه الأسطر الخمسة من كتل تصل إلى 32 بايت في المرة الواحدة ...
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}في حين أنه ليس واضحًا على الفور ، فإن هذا التحقق كافٍ وآمن بنسبة 100٪. هو حقا . لم يتبق سوى عدد قليل من الخطوات التقنية الإضافية غير المكلفة.
نتيجة لذلك ، في معالجات Intel / AMD الحديثة ، يتطلب الأمر أقل من تعليمة واحدة لكل بايت للتحقق حتى من أكثر المدخلات العشوائية غير المرغوب فيها. نظرًا لأن الكود مُحسَّن للغاية ، يمكنك الانتقال إلى ثلاثة تعليمات في كل دورة ، وأكثر من ذلك. أي أننا نستخدم جزءًا صغيرًا من الدورة (أقل من الثلث) لكل بايت إدخال على وحدة المعالجة المركزية الحديثة. وبالتالي ، يتم الحفاظ على سرعة المعالجة بشكل موثوق عند أكثر من 12 جيجابايت / ثانية.
الدرس هو أن جداول البحث المنتظمة مفيدة ، لكن الجداول الموجهة هي اللبنات الأساسية للخوارزميات عالية السرعة.
إذا كنت بحاجة إلى استخدام ميزة التحقق السريع من UTF-8 في الإنتاج ، فنحن نوصي بمكتبة simdjson (الإصدار 0.5 أو أعلى). تم اختباره جيدًا وله ميزات مضمنة مفيدة مثل إرسال وقت التشغيل. على الرغم من أن المكتبة مصممة لتحليل JSON ، إلا أنه يمكنك استخدامها فقط للتحقق من صحة UTF-8 ، حتى إذا لم يكن هناك JSON على الإطلاق. وهو يدعم معالجات 64 بت ARM و x64 ، ولديه أيضًا معالجة احتياطية لوحدات المعالجة المركزية الأخرى. قمنا بتجميعها في ملف رأس واحد مع ملف مصدر واحد ؛ حتى تتمكن من وضعها في مشروع C ++ الخاص بك.
عمل سابق... الميزة الرئيسية في تعميم طريقة التصنيف المتجهية ، والتي هي مفتاح خوارزمية البحث ، تنتمي إلى Mula. على حد علمي ، كان Keizer هو أول من اقترح إستراتيجية البحث الثلاثي الخاصة بنا. تم إنشاء أول خوارزمية تحقق UTF-8 عملية قائمة على SIMD بواسطة K. Willets. قام العديد من الأشخاص ، بما في ذلك Z. Wegner ، بإجراء تحسينات فيه. جاء ترافيس داونز بأفكار ذكية حول كيفية تسريع الخوارزميات التقليدية.
مزيد من القراءة . إذا كنت تستمتع بهذا العمل ، فقد تعجبك مقالات أخرى حول الموضوعات ذات الصلة: "تشفير Base64 وفك تشفيرها بسرعة النسخ في الذاكرة تقريبًا" (البرنامج: الممارسة والخبرة ، 50 (2) ، 2020) و "تحليل غيغابايت من JSON في الثانية" ( مجلة VLDB ، 28 (6) ، 2019).