Foundationপ্রথম নীতি থেকে
LEVEL 1কঠিন~৭ ঘণ্টাPythonCযেকোনো

Mini UTF-8 Codec

Mini UTF-8 Codec

কোনো built-in .encode('utf-8')/.decode('utf-8') ছাড়া, শুধু bit-shifting দিয়ে নিজের UTF-8 encoder আর decoder লেখা — বাংলা যুক্তাক্ষরসহ string দিয়ে টেস্ট করে, malformed byte sequence ধরার validator বানিয়ে।

মাইলস্টোন

আগে যা পড়া দরকার

কেন এই প্রজেক্ট

Unicode/UTF-8 লেসনে আমরা দেখেছি কীভাবে একটা code point ১, ২, ৩ বা ৪ byte-এ ভাগ হয়। কিন্তু “বুঝেছি কীভাবে ভাগ হয়” আর “নিজে সেই bit-shifting লিখতে পারি” — এই দুইয়ের মধ্যে একটা বড় ফাঁক থাকে, আর সেই ফাঁকটাই এই প্রজেক্ট ভরাট করবে।

আসল শিক্ষাটা এনকোডিং-এ নেই — ডিকোডিং-এ। এনকোডিং হলো একমুখী: একটা বৈধ code point সবসময় একটা বৈধ byte sequence দেয়। কিন্তু ডিকোডিং-এ ইনপুট আসে বাইরের জগৎ থেকে — নেটওয়ার্ক থেকে, ফাইল থেকে — আর সেটা যেকোনো byte-এর যেকোনো ক্রম হতে পারে, বৈধ UTF-8 না-ও হতে পারে। তাই “ডিকোডিং মানে এনকোডিং-এর উল্টো কাজ করা” — এই ধারণাটাই ভুল। ডিকোডারকে প্রতিটা ধাপে যাচাই করতে হয় যে যা পড়ছে সেটা আসলেই বৈধ কি না। এই প্রজেক্টের আসল লক্ষ্য সেই validation logic-টা হাতে-কলমে তৈরি করা — যেটা নেটওয়ার্ক প্রোটোকল পার্সার থেকে শুরু করে সিকিউরিটি ফিল্টার পর্যন্ত সবখানে একই প্যাটার্নে ফিরে আসে।

এনকোডিং নিয়ম

Code point পরিসীমাByte সংখ্যাBit প্যাটার্ন
U+0000 – U+007F১0xxxxxxx
U+0080 – U+07FF২110xxxxx 10xxxxxx
U+0800 – U+FFFF (surrogate বাদে)৩1110xxxx 10xxxxxx 10xxxxxx
U+10000 – U+10FFFF৪11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

বাংলা ব্লক (U+0980–U+09FF) পড়ে U+0800-এর ওপরে, তাই প্রতিটা বাংলা অক্ষর ৩ byte নেয় — এটাই নিচে হাতে-কলমে verify করব।

লক্ষ্য

$ python utf8codec.py encode "বিদ্যা"
বিদ্যা → e0 a6 ac e0 a6 bf e0 a6 a6 e0 a7 8d e0 a6 af e0 a6 be
মিলছে built-in .encode('utf-8')-এর সাথে: ✓ (18 bytes)

$ python utf8codec.py test-malformed
OK   invalid continuation byte     : সঠিকভাবে reject হলো
OK   overlong encoding of "/"      : সঠিকভাবে reject হলো
OK   code point out of range       : সঠিকভাবে reject হলো
OK   unpaired surrogate U+D800     : সঠিকভাবে reject হলো

ধাপে ধাপে

১. Encoder — code point থেকে bytes

def encode_codepoint(cp: int) -> bytes:
    if not (0 \<= cp \<= 0x10FFFF):
        raise ValueError(f'অবৈধ code point: U+{cp:X}')
    if 0xD800 \<= cp \<= 0xDFFF:
        raise ValueError(f'surrogate code point encode করা যায় না: U+{cp:X}')

    if cp \<= 0x7F:
        return bytes([cp])
    elif cp \<= 0x7FF:
        b0 = 0xC0 | (cp >> 6)
        b1 = 0x80 | (cp & 0x3F)
        return bytes([b0, b1])
    elif cp \<= 0xFFFF:
        b0 = 0xE0 | (cp >> 12)
        b1 = 0x80 | ((cp >> 6) & 0x3F)
        b2 = 0x80 | (cp & 0x3F)
        return bytes([b0, b1, b2])
    else:
        b0 = 0xF0 | (cp >> 18)
        b1 = 0x80 | ((cp >> 12) & 0x3F)
        b2 = 0x80 | ((cp >> 6) & 0x3F)
        b3 = 0x80 | (cp & 0x3F)
        return bytes([b0, b1, b2, b3])


def encode_utf8(text: str) -> bytes:
    out = bytearray()
    for ch in text:
        out += encode_codepoint(ord(ch))
    return bytes(out)

ord() ব্যবহার করা হচ্ছে শুধু code point বের করতে (সেটা built-in UTF-8 codec না) — আসল bit-shifting কাজটা encode_codepoint-এর ভেতরেই।

হাতে-কলমে একটা উদাহরণ verify করি — বাংলা “ব” (BA, U+09AC = decimal 2476):

cp = 0x09AC = 0000100110101100 (16 bit)
cp >> 12          = 0000              → b0 = 0xE0 | 0x0  = 0xE0
(cp >> 6) & 0x3F   = 100110 = 38(0x26) → b1 = 0x80 | 0x26 = 0xA6
cp & 0x3F          = 101100 = 44(0x2C) → b2 = 0x80 | 0x2C = 0xAC

ফল: E0 A6 AC — যেটা Python-এর 'ব'.encode('utf-8') ঠিক এটাই দেয়।

২. Decoder — leading byte থেকে sequence length

Leading byte-এর উপরের bit-গুলো দেখেই বোঝা যায় পুরো sequence-টা কত byte লম্বা।

def leading_byte_info(b0: int):
    """(sequence length, code point-এর প্রাথমিক bit) রিটার্ন করে।"""
    if b0 \< 0x80:
        return 1, b0
    if b0 & 0xE0 == 0xC0:
        return 2, b0 & 0x1F
    if b0 & 0xF0 == 0xE0:
        return 3, b0 & 0x0F
    if b0 & 0xF8 == 0xF0:
        return 4, b0 & 0x07
    raise ValueError(f'অবৈধ leading byte: 0x{b0:02X}')

লক্ষ্য করুন — এই ফাংশনটাই একটা continuation byte (10xxxxxx, অর্থাৎ 0x80–0xBF) কে leading byte হিসেবে দিলে reject করে, কারণ সেটা উপরের চারটা if-এর কোনোটাতেই মেলে না।

৩. পূর্ণ decode + validation

MIN_CP_FOR_LENGTH = {1: 0, 2: 0x80, 3: 0x800, 4: 0x10000}

def decode_one(data: bytes, i: int):
    b0 = data[i]
    length, cp = leading_byte_info(b0)

    if i + length > len(data):
        raise ValueError(f'position {i}: {length}-byte sequence-এর জন্য পর্যাপ্ত byte নেই')

    for k in range(1, length):
        b = data[i + k]
        if b & 0xC0 != 0x80:
            raise ValueError(
                f'position {i + k}: continuation byte (10xxxxxx) আশা করেছিলাম, '
                f'পেলাম 0x{b:02X}'
            )
        cp = (cp \<\< 6) | (b & 0x3F)

    if cp \< MIN_CP_FOR_LENGTH[length]:
        raise ValueError(
            f'position {i}: overlong encoding — U+{cp:04X}-কে {length} byte দিয়ে '
            f'লেখা হয়েছে, ছোট encoding-এই যথেষ্ট ছিল'
        )
    if 0xD800 \<= cp \<= 0xDFFF:
        raise ValueError(f'position {i}: unpaired surrogate U+{cp:04X} — UTF-8-এ অবৈধ')
    if cp > 0x10FFFF:
        raise ValueError(f'position {i}: code point পরিসীমার বাইরে: U+{cp:X}')

    return cp, i + length


def decode_utf8(data: bytes) -> list:
    codepoints = []
    i = 0
    while i \< len(data):
        cp, i = decode_one(data, i)
        codepoints.append(cp)
    return codepoints

চারটা আলাদা ব্যর্থতার কারণ খেয়াল করুন — প্রতিটাই ভিন্ন বাস্তব bug/আক্রমণ প্রতিনিধিত্ব করে:

  • Continuation byte ভুল — ডেটা করাপশন বা truncated stream
  • Overlong encoding — একই code point-কে ইচ্ছাকৃতভাবে বেশি byte দিয়ে লেখা, historically security filter bypass করতে ব্যবহৃত হয়েছে (নিচে দেখুন)
  • Out-of-range code point — Unicode-এর নিজস্ব সীমা (U+10FFFF পর্যন্ত) লঙ্ঘন
  • Unpaired surrogate — UTF-16-এর জন্য সংরক্ষিত code point (U+D800–U+DFFF) UTF-8-এ কখনো সরাসরি আসার কথা না

৪. বাংলা যুক্তাক্ষরসহ string দিয়ে round-trip টেস্ট

“বিদ্যা” শব্দে একটা যুক্তাক্ষর আছে — দ + ্ (হসন্ত) + য = “দ্য” ligature। এনকোডারের চোখে এটা আলাদা কিছু না, শুধু ৬টা code point পরপর — কিন্তু এটাই grapheme cluster লেসনের মূল কথা: একটা “অক্ষর” যা চোখে দেখা যায়, আর একটা Unicode code point — এই দুইটা এক জিনিস না।

def selftest():
    samples = ["A", "café", "বিদ্যা", "😀", ""]
    for s in samples:
        mine = encode_utf8(s)
        builtin = s.encode('utf-8')
        assert mine == builtin, f'{s!r}: mismatch — mine={mine.hex()} builtin={builtin.hex()}'

        decoded_cps = decode_utf8(mine)
        decoded_str = ''.join(chr(cp) for cp in decoded_cps)
        assert decoded_str == s, f'{s!r}: round-trip ব্যর্থ, পেলাম {decoded_str!r}'

        print(f'OK  {s!r:12} → {mine.hex(" ")}  ({len(mine)} bytes)')

chr() দিয়ে code point থেকে আবার string বানানো হচ্ছে — এটাও built-in UTF-8 codec না, শুধু code point ↔ character mapping।

৫. Malformed input দিয়ে validator টেস্ট

চারটা টেস্ট ভেক্টর, প্রতিটাই বাস্তব জগতের একটা পরিচিত কেস:

MALFORMED_CASES = [
    (bytes([0xE0, 0x41, 0xAC]), 'invalid continuation byte'),
    (bytes([0xC0, 0xAF]),       'overlong encoding of "/"'),
    (bytes([0xF7, 0xBF, 0xBF, 0xBF]), 'code point out of range'),
    (bytes([0xED, 0xA0, 0x80]), 'unpaired surrogate U+D800'),
]

def test_malformed():
    for data, label in MALFORMED_CASES:
        try:
            decode_utf8(data)
            print(f'FAIL {label}: ভুলভাবে accept হয়ে গেছে!')
        except ValueError as e:
            print(f'OK   {label}: সঠিকভাবে reject হলো — {e}')

0xC0 0xAF বিশেষভাবে কুখ্যাত — এটা / (U+002F, normally ১ byte-এই লেখা হয়) কে জোর করে ২ byte-এ লেখার overlong encoding। পুরনো IIS সার্ভারে এই ট্রিকটা path-traversal ফিল্টার bypass করতে ব্যবহৃত হয়েছিল, কারণ ফিল্টার শুধু raw / byte (0x2F) খুঁজত, decode করার আগে — decode করার পরে এটা ঠিকই / হয়ে যেত। এটাই “validate করার আগে normalize করো” নিয়মের ইতিহাস।

নিজেকে চ্যালেঞ্জ করুন

  1. UTF-16 encoder/decoder যোগ করুন — surrogate pair-এর গণিত (high/low surrogate কম্বিনেশন) নিজে লিখুন
  2. Streaming decoder বানান — পুরো buffer একসাথে না দিয়ে byte-by-byte feed করলেও কাজ করবে এমন state machine
  3. Grapheme cluster segmentation যোগ করুন — বাংলা conjunct-গুলো কোথায় “একটা অক্ষর” হিসেবে ভাঙা উচিত, তার নিয়ম লিখুন
  4. CESU-8 detector — যে ডেটা surrogate pair-কে UTF-16-এর মতো আলাদা আলাদা এনকোড করেছে, সেটা চিহ্নিত করুন
  5. Fuzz testing — লক্ষ লক্ষ random byte sequence generate করে আপনার decoder কখনো crash করে কি না, Python-এর built-in decoder-এর সাথে accept/reject সিদ্ধান্ত মেলে কি না যাচাই করুন

এটা যেখানে গিয়ে মিশবে

এখানে যা শিখলেনপরে কোথায় লাগবে
Leading-byte state machineLevel 5 — Compiler lexer, ছোট state machine দিয়ে টোকেন চেনা
Byte-by-byte stream validationLevel 7 — Network protocol parser, malformed packet handle করা
Overlong encoding-এর মতো bypass ট্রিকLevel 10 — Input validation, encoding-based injection attack
DFA-স্টাইল leading/continuation নিয়মLevel 13 — Regex Engine প্রজেক্ট, DFA-ভিত্তিক matcher
Text encoding সঠিকভাবে সংরক্ষণLevel 8 — Database-এ collation ও encoding সংক্রান্ত bug এড়ানো