சுழல்-நீள முன்னொட்டு (RLP) தொடராக்கம்

எத்தேரியத்தின் செயலாக்க கிளையண்டுகளில் சுழல்-நீள முன்னொட்டு (Recursive Length Prefix - RLP) தொடராக்கம் பரவலாகப் பயன்படுத்தப்படுகிறது. RLP ஆனது முனைகளுக்கு இடையிலான தரவுப் பரிமாற்றத்தை இட-திறனுள்ள வடிவத்தில் தரப்படுத்துகிறது. RLP இன் நோக்கம் தன்னிச்சையாக உள்ளமைக்கப்பட்ட பைனரி தரவுகளின் வரிசைகளைக் குறியாக்குவதாகும், மேலும் எத்தேரியத்தின் செயலாக்க அடுக்கில் உள்ள பொருட்களைத் தொடராக்கப் பயன்படுத்தப்படும் முதன்மைக் குறியாக்க முறை RLP ஆகும். RLP இன் முக்கிய நோக்கம் கட்டமைப்பைக் குறியாக்குவதாகும்; நேர்மறை முழு எண்களைத் தவிர, RLP குறிப்பிட்ட தரவு வகைகளை (எ.கா., சரங்கள், மிதவைகள்) குறியாக்குவதை உயர்-வரிசை நெறிமுறைகளுக்கு வழங்குகிறது. நேர்மறை முழு எண்கள் முன்னணி பூஜ்ஜியங்கள் இல்லாமல் பிக்-எண்டியன் (big-endian) பைனரி வடிவத்தில் குறிப்பிடப்பட வேண்டும் (இதனால் முழு எண் மதிப்பு பூஜ்ஜியமானது வெற்று பைட் வரிசைக்குச் சமமாகிறது). முன்னணி பூஜ்ஜியங்களைக் கொண்ட தொடராக்கம் நீக்கப்பட்ட நேர்மறை முழு எண்கள் RLP ஐப் பயன்படுத்தும் எந்தவொரு உயர்-வரிசை நெறிமுறையாலும் செல்லாததாகக் கருதப்பட வேண்டும்.

மேலும் தகவல்களுக்கு எத்தேரியம் மஞ்சள் தாள் (பின்னிணைப்பு B) (opens in a new tab) ஐப் பார்க்கவும்.

ஒரு அகராதியைக் குறியாக்க RLP ஐப் பயன்படுத்த, பரிந்துரைக்கப்பட்ட இரண்டு நியமன வடிவங்கள்:

• அகராதி வரிசையில் விசைகளுடன் [[k1,v1],[k2,v2]...] ஐப் பயன்படுத்தவும்
• எத்தேரியம் செய்வது போல உயர்-நிலை பாட்ரிசியா மரக் (Patricia Tree) குறியாக்கத்தைப் பயன்படுத்தவும்

வரையறை

RLP குறியாக்கச் செயல்பாடு ஒரு உருப்படியை எடுத்துக்கொள்கிறது. ஒரு உருப்படி பின்வருமாறு வரையறுக்கப்படுகிறது:

• ஒரு சரம் (அதாவது, பைட் வரிசை) ஒரு உருப்படி
• உருப்படிகளின் பட்டியல் ஒரு உருப்படி
• ஒரு நேர்மறை முழு எண் ஒரு உருப்படி

எடுத்துக்காட்டாக, பின்வருவன அனைத்தும் உருப்படிகள்:

• ஒரு வெற்றுச் சரம்;
• "cat" என்ற சொல்லைக் கொண்ட சரம்;
• எந்த எண்ணிக்கையிலான சரங்களையும் கொண்ட ஒரு பட்டியல்;
• மற்றும் ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"] போன்ற மிகவும் சிக்கலான தரவுக் கட்டமைப்புகள்.
• 100 என்ற எண்

இந்தப் பக்கத்தின் எஞ்சிய பகுதியின் சூழலில், 'சரம்' என்பது "குறிப்பிட்ட எண்ணிக்கையிலான பைனரி தரவுகளின் பைட்டுகள்" என்று பொருள்படும் என்பதை நினைவில் கொள்ளவும்; சிறப்பு குறியாக்கங்கள் எதுவும் பயன்படுத்தப்படவில்லை, மேலும் சரங்களின் உள்ளடக்கம் பற்றிய எந்த அறிவும் குறிக்கப்படவில்லை (குறைந்தபட்சம் அல்லாத நேர்மறை முழு எண்களுக்கு எதிரான விதியால் தேவைப்படுவதைத் தவிர).

RLP குறியாக்கம் பின்வருமாறு வரையறுக்கப்படுகிறது:

• ஒரு நேர்மறை முழு எண்ணுக்கு, அது குறுகிய பைட் வரிசையாக மாற்றப்படுகிறது, அதன் பிக்-எண்டியன் விளக்கம் முழு எண்ணாகும், பின்னர் கீழே உள்ள விதிகளின்படி ஒரு சரமாகக் குறியாக்கப்படுகிறது.
• [0x00, 0x7f] (தசம [0, 127]) வரம்பில் உள்ள மதிப்பைக் கொண்ட ஒற்றை பைட்டுக்கு, அந்த பைட் அதன் சொந்த RLP குறியாக்கமாகும்.
• இல்லையெனில், ஒரு சரம் 0-55 பைட்டுகள் நீளமாக இருந்தால், RLP குறியாக்கம் 0x80 (தசம 128) மதிப்பைக் கொண்ட ஒற்றை பைட்டையும், சரத்தின் நீளத்தையும், அதைத் தொடர்ந்து சரத்தையும் கொண்டிருக்கும். முதல் பைட்டின் வரம்பு இதனால் [0x80, 0xb7] (தசம [128, 183]) ஆகும்.
• ஒரு சரம் 55 பைட்டுகளுக்கு மேல் நீளமாக இருந்தால், RLP குறியாக்கம் 0xb7 (தசம 183) மதிப்பைக் கொண்ட ஒற்றை பைட்டையும், பைனரி வடிவத்தில் சரத்தின் நீளத்தின் பைட்டுகளில் உள்ள நீளத்தையும், அதைத் தொடர்ந்து சரத்தின் நீளத்தையும், அதைத் தொடர்ந்து சரத்தையும் கொண்டிருக்கும். எடுத்துக்காட்டாக, 1024 பைட் நீளமுள்ள சரம் \xb9\x04\x00 (தசம 185, 4, 0) ஆகக் குறியாக்கப்பட்டு அதைத் தொடர்ந்து சரம் வரும். இங்கே, 0xb9 (183 + 2 = 185) முதல் பைட்டாகவும், அதைத் தொடர்ந்து உண்மையான சரத்தின் நீளத்தைக் குறிக்கும் 2 பைட்டுகள் 0x0400 (தசம 1024) ஆகவும் இருக்கும். முதல் பைட்டின் வரம்பு இதனால் [0xb8, 0xbf] (தசம [184, 191]) ஆகும்.
• ஒரு சரம் 2^64 பைட்டுகள் நீளமாகவோ அல்லது அதற்கு மேலாகவோ இருந்தால், அது குறியாக்கப்படாமல் போகலாம்.
• ஒரு பட்டியலின் மொத்த பேலோடு (அதாவது, RLP குறியாக்கம் செய்யப்படும் அதன் அனைத்து உருப்படிகளின் ஒருங்கிணைந்த நீளம்) 0-55 பைட்டுகள் நீளமாக இருந்தால், RLP குறியாக்கம் 0xc0 மதிப்பைக் கொண்ட ஒற்றை பைட்டையும், பேலோடின் நீளத்தையும், அதைத் தொடர்ந்து உருப்படிகளின் RLP குறியாக்கங்களின் இணைப்பையும் கொண்டிருக்கும். முதல் பைட்டின் வரம்பு இதனால் [0xc0, 0xf7] (தசம [192, 247]) ஆகும்.
• ஒரு பட்டியலின் மொத்த பேலோடு 55 பைட்டுகளுக்கு மேல் நீளமாக இருந்தால், RLP குறியாக்கம் 0xf7 மதிப்பைக் கொண்ட ஒற்றை பைட்டையும், பைனரி வடிவத்தில் பேலோடின் நீளத்தின் பைட்டுகளில் உள்ள நீளத்தையும், அதைத் தொடர்ந்து பேலோடின் நீளத்தையும், அதைத் தொடர்ந்து உருப்படிகளின் RLP குறியாக்கங்களின் இணைப்பையும் கொண்டிருக்கும். முதல் பைட்டின் வரம்பு இதனால் [0xf8, 0xff] (தசம [248, 255]) ஆகும்.

சுருக்கமான வடிவத்தில்:

• p = பேலோடு (payload)
• n = நீளம் (பேலோடு பைட்டுகளின் எண்ணிக்கை)
• N = நீளத்தின்-நீள ஆஃப்செட் (N+1 n பைட்டுகள் தொடரும்)

குறியீட்டில், இது:

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80:
            return input
        return encode_length(len(input), 0x80) + input
    elif isinstance(input, list):
        output = ''
        for item in input:
            output += rlp_encode(item)
        return encode_length(len(output), 0xc0) + output

def encode_length(L, offset):
    if L < 56:
         return chr(L + offset)
    elif L < 256**8:
         BL = to_binary(L)
         return chr(len(BL) + offset + 55) + BL
    raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    return to_binary(int(x / 256)) + chr(x % 256)

எடுத்துக்காட்டுகள்

• "dog" என்ற சரம் = [ 0x83, 'd', 'o', 'g' ]
• [ "cat", "dog" ] என்ற பட்டியல் = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
• வெற்றுச் சரம் ('null') = [ 0x80 ]
• வெற்றுப் பட்டியல் = [ 0xc0 ]
• முழு எண் 0 = [ 0x80 ]
• பைட் '\x00' = [ 0x00 ]
• பைட் '\x0f' = [ 0x0f ]
• பைட்டுகள் '\x04\x00' = [ 0x82, 0x04, 0x00 ]
• மூன்றின் கணக் கோட்பாட்டுப் பிரதிநிதித்துவம் (opens in a new tab), [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
• "Lorem ipsum dolor sit amet, consectetur adipisicing elit" என்ற சரம் = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

RLP குறியாக்க நீக்கம்

RLP குறியாக்கத்தின் விதிகள் மற்றும் செயல்முறையின்படி, RLP குறியாக்க நீக்கத்தின் உள்ளீடு பைனரி தரவுகளின் வரிசையாகக் கருதப்படுகிறது. RLP குறியாக்க நீக்கச் செயல்முறை பின்வருமாறு:

1. உள்ளீட்டுத் தரவின் முதல் பைட்டின் (அதாவது, முன்னொட்டு) படி மற்றும் தரவு வகையைக் குறியாக்க நீக்கம் செய்தல், உண்மையான தரவின் நீளம் மற்றும் ஆஃப்செட்;

2. தரவின் வகை மற்றும் ஆஃப்செட்டின் படி, நேர்மறை முழு எண்களுக்கான குறைந்தபட்ச குறியாக்க விதியை மதித்து, தரவை அதற்கேற்ப குறியாக்க நீக்கம் செய்தல்;

3. உள்ளீட்டின் எஞ்சிய பகுதியைக் குறியாக்க நீக்கம் செய்வதைத் தொடர்தல்;

அவற்றில், தரவு வகைகள் மற்றும் ஆஃப்செட்டைக் குறியாக்க நீக்கம் செய்வதற்கான விதிகள் பின்வருமாறு:

1. முதல் பைட்டின் (அதாவது, முன்னொட்டு) வரம்பு [0x00, 0x7f] ஆக இருந்தால் தரவு ஒரு சரமாகும், மேலும் சரம் முதல் பைட்டே ஆகும்;

2. முதல் பைட்டின் வரம்பு [0x80, 0xb7] ஆக இருந்தால் தரவு ஒரு சரமாகும், மேலும் முதல் பைட்டிலிருந்து 0x80 ஐக் கழித்தால் கிடைக்கும் நீளத்திற்குச் சமமான சரம் முதல் பைட்டைத் தொடர்ந்து வரும்;

3. முதல் பைட்டின் வரம்பு [0xb8, 0xbf] ஆக இருந்தால் தரவு ஒரு சரமாகும், மேலும் முதல் பைட்டிலிருந்து 0xb7 ஐக் கழித்தால் கிடைக்கும் பைட்டுகளில் உள்ள நீளத்திற்குச் சமமான சரத்தின் நீளம் முதல் பைட்டைத் தொடர்ந்து வரும், மேலும் சரம் சரத்தின் நீளத்தைத் தொடர்ந்து வரும்;

4. முதல் பைட்டின் வரம்பு [0xc0, 0xf7] ஆக இருந்தால் தரவு ஒரு பட்டியலாகும், மேலும் முதல் பைட்டிலிருந்து 0xc0 ஐக் கழித்தால் கிடைக்கும் மொத்த பேலோடுக்குச் சமமான பட்டியலின் அனைத்து உருப்படிகளின் RLP குறியாக்கங்களின் இணைப்பு முதல் பைட்டைத் தொடர்ந்து வரும்;

5. முதல் பைட்டின் வரம்பு [0xf8, 0xff] ஆக இருந்தால் தரவு ஒரு பட்டியலாகும், மேலும் முதல் பைட்டிலிருந்து 0xf7 ஐக் கழித்தால் கிடைக்கும் நீளத்திற்குச் சமமான பட்டியலின் மொத்த பேலோடு முதல் பைட்டைத் தொடர்ந்து வரும், மேலும் பட்டியலின் அனைத்து உருப்படிகளின் RLP குறியாக்கங்களின் இணைப்பு பட்டியலின் மொத்த பேலோடைத் தொடர்ந்து வரும்;

குறியீட்டில், இது:

def rlp_decode(input):
    if len(input) == 0:
        return
    output = ''
    (offset, dataLen, type) = decode_length(input)
    if type is str:
        output = instantiate_str(substr(input, offset, dataLen))
    elif type is list:
        output = instantiate_list(substr(input, offset, dataLen))
    output += rlp_decode(substr(input, offset + dataLen))
    return output

def decode_length(input):
    length = len(input)
    if length == 0:
        raise Exception("input is null")
    prefix = ord(input[0])
    if prefix <= 0x7f:
        return (0, 1, str)
    elif prefix <= 0xb7 and length > prefix - 0x80:
        strLen = prefix - 0x80
        return (1, strLen, str)
    elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
        lenOfStrLen = prefix - 0xb7
        strLen = to_integer(substr(input, 1, lenOfStrLen))
        return (1 + lenOfStrLen, strLen, str)
    elif prefix <= 0xf7 and length > prefix - 0xc0:
        listLen = prefix - 0xc0;
        return (1, listLen, list)
    elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
        lenOfListLen = prefix - 0xf7
        listLen = to_integer(substr(input, 1, lenOfListLen))
        return (1 + lenOfListLen, listLen, list)
    raise Exception("input does not conform to RLP encoding form")

def to_integer(b):
    length = len(b)
    if length == 0:
        raise Exception("input is null")
    elif length == 1:
        return ord(b[0])
    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256

மேலும் படிக்க

• எத்தேரியத்தில் RLP (opens in a new tab)
• எத்தேரியத்தின் திரைக்குப் பின்னால்: RLP (opens in a new tab)
• காக்லியோ, ஏ. (2020). ACL2 இல் எத்தேரியத்தின் சுழல் நீள முன்னொட்டு. arXiv முன்அச்சு arXiv:2009.13769. (opens in a new tab)

தொடர்புடைய தலைப்புகள்

• பாட்ரிசியா மெர்க்கிள் ட்ரை (Patricia merkle trie)