আপনি শাখা ছাড়া UTF-8 এনকোড করতে পারেন?
প্রশ্ন
ক পুনরাবৃত্তি আড্ডা নাথান গোল্ডবাউম জিজ্ঞাসা করা হয়েছে:
আমি জানি কিভাবে বিটম্যাথ এবং কিছু LUT ব্যবহার করে UTF-8 ডিকোড করতে হয় (দেখুন https://github.com/skeeto/branchless-utf8), কিন্তু যদি আমি একটি কোডপয়েন্ট থেকে UTF-8 এ যেতে চাই, তাহলে শাখা ছাড়াই এটি করার একটি উপায় আছে কি?
শুরু করার জন্য, এই C ফাংশনটি লেখার একটি উপায় আছে, যা কোন শাখা ছাড়াই কোডপয়েন্টের জন্য UTF-8 বাইট সংরক্ষণ করার জন্য প্রয়োজনীয় বাইটের সংখ্যা প্রদান করে? নাকি আমার একটা বিশাল লুক-আপ-টেবিল লাগবে?
সি ফাংশন
int num_utf8_bytes_for_codepoint(uint32_t code) if (code <= 0x7F) return 1; else if (code <= 0x07FF) return 2; else if (code <= 0xFFFF) if ((code >= 0xD800) && (code <= 0xDFFF)) // surrogates are invalid UCS4 code points return -1; return 3; else if (code <= 0x10FFFF) return 4; else // codepoint is outside the valid unicode range return -1;
আমি এটি নিয়ে চিন্তা করেছি কিন্তু অবিলম্বে একটি বিশাল (2^32) লুকআপ টেবিল ছাড়া এটি করার উপায় দেখতে পাইনি।
প্রায় উত্তর
পর্যন্ত লরেঞ্জ নির্দেশিত:
খুব হ্যান্ডওয়েভি আইডিয়া: একটি 32 বিট কোড পয়েন্ট utf8 এ এনকোড করুন কিন্তু ফলাফলটি আবার 32 বিট শব্দে সংরক্ষণ করুন। কতগুলি বাইট প্রয়োজন তা বের করতে অগ্রণী/পরবর্তী শূন্যের সংখ্যা গণনা করুন। আউটপুট বাফারে চারটি বাইট লিখুন তবে আপনার সত্যিই প্রয়োজনীয় বাইটের সংখ্যার দ্বারা আউটপুটে আপনার অবস্থানকে অগ্রসর করুন।
আহা!
অগ্রণী শূন্যের সংখ্যা 12 থেকে 32 পর্যন্ত হবে – একটি লুকআপ টেবিলের জন্য একটি খুব যুক্তিসঙ্গত আকার। সেখান থেকে, আমরা দৈর্ঘ্য অনুসারে অন্যান্য পরামিতি দেখতে পারি (4টির বেশি নয়)।
আমি চ্যাটে একটি খসড়া বাদ দিয়েছিলাম, তারপর সন্ধ্যায় এটি পরীক্ষা করতে (এবং ঠিক করতে) ফিরে এসেছি। যখন আমি পরীক্ষায় উত্তীর্ণ হয়েছিলাম, তখন এটি দেখতে এইরকম ছিল:
/// Return the number of bytes required to UTF-8 encode a codepoint.
/// Returns 0 for surrogates and out-of-bounds values.
const fn utf8_bytes_for_codepoint(codepoint: u32) -> usize exceeded_bit << 1
/// Length, based on the number of leading zeros.
const LEN: (u8; 33) = (
// 0-10 leading zeros: not valid
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
// 11-15 leading zeros: 4 bytes
4, 4, 4, 4, 4,
//16-20 leading zeros: 3 bytes
3, 3, 3, 3, 3,
// 21-24 leading zeros: 2 bytes
2, 2, 2, 2,
// 25-32 leading zeros: 1 byte
1, 1, 1, 1, 1, 1, 1, 1,
);
/// Encode a UTF-8 codepoint.
/// Returns a buffer and the number of valid bytes in the buffer.
///
/// To add this codepoint to a string, append all four bytes in order,
/// and record that (usize) bytes were added to the string.
///
/// Returns a length of zero for invalid codepoints (surrogates and out-of-bounds values).
pub fn branchless_utf8(codepoint: u32) -> ((u8; 4), usize) ((codepoint >> SHIFT(len)(3)) & MASK(len)(3) as u32) as u8,
);
(buf, len)
type Table = ((u8; 4); 5);
// Byte prefix for a continuation byte.
const CONTINUE: u8 = 0b1000_0000;
const PREFIX: Table = (
(0u8; 4),
(0, 0, 0, 0),
(0b1100_0000, CONTINUE, 0, 0),
(0b1110_0000, CONTINUE, CONTINUE, 0),
(0b1111_0000, CONTINUE, CONTINUE, CONTINUE),
);
// We must arrange that the most-significant bytes are always in byte 0.
const SHIFT: Table = (
(0u8; 4),
(0, 0, 0, 0),
(6, 0, 0, 0),
(12, 6, 0, 0),
(18, 12, 6, 0),
);
const MASK: Table = (
(0u8; 4),
(0x7f, 0, 0, 0),
(0x1f, 0x3f, 0, 0),
(0x0f, 0x3f, 0x3f, 0),
(0x07, 0x3f, 0x3f, 0x3f),
);
শাখা
বিবৃতি, লুপ, বা অন্যান্য শর্তসাপেক্ষ হলে না। তাই, শাখাহীন, তাই না?
…আচ্ছা, না। আমরা যদি উঁকি দিয়ে দেখি (অপ্টিমাইজ করা) কোড কম্পাইলার এক্সপ্লোরারে, আমরা দেখতে পাচ্ছি x86_64 অ্যাসেম্বলি আছে দুটি ভিন্ন ধরনের শাখা.
অগ্রণী শূন্য গণনা করুন
ফাংশনের শুরুতে একটি শাখা আছে:
test esi, esi
je .LBB0_1
bsr eax, esi
xor eax, 31
jmp .LBB0_3
.LBB0_1:
mov eax, 32
.LBB0_3:
mov eax, eax
আমি এটির মধ্য দিয়ে না যাওয়া পর্যন্ত আমি নিশ্চিত ছিলাম না যে এটি কী ছিল। “বিশেষ” ক্ষেত্রে মনে হয় যখন ইনপুট (esi) শূন্য; তারপর এটি 32 রিটার্ন করে।
বিশেষ ক্ষেত্রে কেন? এর জন্য কম্পাইলার এক্সপ্লোরারের টুলটিপ bsr নির্দেশ বলে:
কন্টেন্ট সোর্স অপারেন্ড 0 হলে, গন্তব্য অপারেন্ডের বিষয়বস্তু অনির্ধারিত।
সুতরাং x86_64 প্রসেসরে, আমাদের বলতে হবে “একটি 32-বিট শূন্য মানের 32টি অগ্রণী শূন্য”। ভিন্নভাবে বললে, “গণনা অগ্রণী শূন্য” অন্তর্নিহিত অগত্যা একটি শাখাবিহীন নির্দেশ নয়। এটি অন্য স্থাপত্যে সুন্দর দেখাতে পারে!
সীমানা চেক
অন্য লাফটি বেশ কয়েকটি অ্যারে-বাউন্ড চেকের সংমিশ্রণ বলে মনে হচ্ছে।
cmp eax, 4
ja .LBB0_5
...
LBB0_5:
lea rdx, (rip + .L__unnamed_5)
mov esi, 5
mov rdi, rax
call qword ptr (rip + core::panicking::panic_bounds_check::h8307ccead484a122@GOTPCREL)
সমস্ত জাম্প অ্যারে একই আবদ্ধ (4), তাই কম্পাইলার শুধুমাত্র একবার পরীক্ষা করার সিদ্ধান্ত নিতে পারে – এবং এখনও রাস্টের বিখ্যাত নিরাপত্তা গ্যারান্টি পেতে পারে।
নীতিগতভাবে, যদি কম্পাইলার এর মাধ্যমে অপ্টিমাইজ করে LEN টেবিল, এটি এই চেকটিও বাদ দিতে পারে; দ LEN মান কখনই 4-এর বেশি নয়, যা সমস্ত টেবিলের জন্য একটি বৈধ সূচক। কিন্তু স্পষ্টতই ধ্রুবকগুলি এতদূর প্রচার করে না।
শাখা নির্মূল
কোড পরিবর্তন এবং ড্রপ অনিরাপদ অ্যারে অ্যাক্সেস
অ্যারে বাউন্ড চেক বাদ দেয়। কিন্তু এখনও, শুরুতে গণনা-নেতৃস্থানীয়-শূন্য শাখা এখনও আছে। আমরা কি পরিত্রাণ পেতে পারি?
আসুন কোডের একটি বিটটি আরেকটু দেখে নেওয়া যাক – বিশেষত, আমরা কীভাবে সীমার বাইরের মানগুলি পরিচালনা করি:
let exceeded_bit = (codepoint > 0x10_FFFF) as usize;
আমি এখানে যে কৌশলটি টেনেছি তা হল একটি পূর্ণসংখ্যা (1 বা 0) এ বুলিয়ান (সত্য বা মিথ্যা) নিক্ষেপ করা। রাস্টের শব্দার্থবিদ্যা গ্যারান্টি দেয় যে এই রূপান্তর নিরাপদ, এবং এটি এমন একটি উপস্থাপনা হতে পারে যার সাথে হার্ডওয়্যার কাজ করতে পারে; এটি সংকলনের পর শর্তসাপেক্ষ হবে বলে মনে হয় না।
আমি শূন্যে মাস্কিং সঞ্চালনের জন্য এই বুলিয়ান-এ-পূর্ণসংখ্যা ব্যবহার করেছি। কিন্তু আপনি কি জানেন আমরা পূর্ণসংখ্যা দিয়ে আর কি করতে পারি?
সংযোজন।
উত্তর
দৈর্ঘ্য-কম্পিউটিং ফাংশনটি টুইক করে আমরা সমস্ত শাখা থেকে পরিত্রাণ পেতে পারি:
const fn utf8_bytes_for_codepoint(codepoint: u32) -> usize surrogate_bit;
let exceeded_bit = (codepoint > 0x10_FFFF) as usize;
let exceeded_mask = exceeded_bit << 2
এটি নাথনের মূল প্রশ্নের উত্তর, বাইটের সংখ্যা বের করার বিষয়ে। কম্পাইলার এক্সপ্লোরার নিশ্চিত করে যে, অপ্টিমাইজেশন সক্ষম করে, এই ফাংশন শাখাহীন.
আনন্দের বিষয়, এই রূপান্তরটিও কম্পাইলারকে উপলব্ধি করার অনুমতি দিয়েছে len <= 4 সমস্ত পাথে, এবং স্থিরভাবে অ্যারে বাউন্ড চেক মুছে ফেলার জন্য। মানে সম্পূর্ণ কোড পাশাপাশি শাখাবিহীন। বিজয় !
সতর্কতা
এই যখন শাখাবিহীনআমি এটা যে একেবারে কোন দাবি করা অপ্টিমাইজ করা – এখানে আমার একমাত্র লক্ষ্য ছিল শাখাহীনতার ধারণার প্রমাণ। আমি এমনকি এটা বেঞ্চমার্ক না!
ক্রিস ওয়েলনস নোট করেছেন শাখাবিহীন ডিকোডিং সম্পর্কে তার পোস্ট
যে একটি DFA-ভিত্তিক ডিকোডারের অনুরূপ কর্মক্ষমতা থাকতে পারে; SIMD এবং অন্যান্য “হার্ডওয়্যার আপনাকে যা দেয় তা ব্যবহার করুন” কৌশলগুলি সম্ভবত আরও ভাল। আমি আপনার প্রিয় স্ট্যান্ডার্ড লাইব্রেরির একটির উপর আমার এনকোডারে বাজি ধরব না।
আমি উপযোগিতা কোন দাবি করা. কিন্তু কোডের সাথে যেকোন কিছু করতে আপনাকে স্বাগত জানাই: আমি এমআইটি লাইসেন্সের অধীনে এটি প্রকাশ করছি। সম্পূর্ণ কোডটি এখানে রয়েছে, পরীক্ষার সাথে আমি এটিকে রাস্টের বাস্তবায়নের সাথে মেলে।
ধন্যবাদ!
প্রশ্নটির জন্য নাথান এবং অন্তর্দৃষ্টির জন্য লরেঞ্জকে ধন্যবাদ! কোন ভুল বাকি আছে আমার নিজের – আপনি যদি তাদের খুঁজে আমাকে একটি চিৎকার দিন!
