ASN1标準對OID的編碼

asn1對OID的編碼有一些規定，形如a.b.c.d.e的OID被編碼的時候，完全可以按照der的編碼規則将整個oid的類型設定為object，然後将每一個點分數字的類型設定為integer，最終編碼為[obj|length[[int|lena[a]]][int|lenb[b]][int|lenc[c]]...]，可是asn1标準并沒有如此編碼，而是使用了"more bit"這種方式，這樣就少了很多的層次，不必為每一個點分數字進行asn1編碼，具體說來就是将一個點分數字拆分為7bit一組的序列，然後除了最後一個的最高位填入0之外其餘的最高位都填1，然後将它們合并在一起，最終将每一個經過這樣處理的點分數字連接配接在一起，可以減少編碼的長度，起碼每個點分數字的type和length都省略了，唯一的不足是8bit的點分數字要編碼為16bits。

     以上僅僅是對oid編碼的規定之一，還有一個很有意思的就是由于OID的前兩極的辨別數字都不是很大，是以更好的辦法就是将OID的前兩級編碼到一個7bit的數中(由于辨別more bit需要最高位，是以隻剩下7位可以存資料)，第一級OID隻有3個，分别是itu-t(0)，iso(1)，joint-iso-itu-t(2)，并且第二級OID辨別最多也就23，挂于joint-iso-itu-t之下，現在需要一個算法，将第一級和第二級的OID辨別編碼到一個7bit的數裡面，這就需要用一種平坦的方式來索引前兩級的資料，構造一組虛拟的辨別，為了對待三個一級OID辨別更公平，最好是将127個“位置”平均分到三個一級辨別，于是就将127除以3，結果是40，于是頭40個虛拟辨別分給itu-t，中間40個分給iso，後面的47個分給joint-iso-itu-t，這樣，前兩級是a.b的OID的a和b就被編碼成了40*a+b，如此也就節省了一個編碼byte。本質上這種編碼的思想是在分級的辨別上構造一組平坦的虛拟辨別。

     實際上為何不采用x86的頁表的形式(或者說是trie樹的形式)來進行編碼呢，将127，也就是7個bit分成3個段，0-x為第一級索引，x+1-6位第二級索引...事實上這個想法是很不錯的，但是看一下真實的情況，由于第二級最大的OID辨別數是23，二進制為10111，又因為隻能使用7個bit，則唯一的方案就是0-1bit為第一級索引，2-6bit為第二級索引，5個bit最大隻能表示32，是以joint-iso-itu-t下還剩下9個可用的位置，雖然說root下面還有一個位置，而該位置下能挂32個二級位置，但是OID是國際機構的人定義的，這就存在很大的不穩定性，雖說7bit數能包容的總的虛拟位置是一定的，但是怎樣對應這些平坦虛拟位置的真實分級位置卻存在很大的人為因素，在root下增加一個節點的可能性不大，那意味的一個新的頂級機構的産生，但是在已經存在的機構下産生一個分支卻是正常的，故joint-iso-itu-t下增加新節點的可能性要比root下增加新節點的可能性大得多，asn1的編碼方案為joint-iso-itu-t留下了11個空閑位置，而類似trie樹的編碼方案隻留下了确定的9個位置，孰優孰劣？看看同樣都是二級辨別，joint-iso-itu-t下面有23個節點，而itu-t下面卻隻有3個，然後就知道這樣人為因素很大的系統是多麼不适合在計算機中普遍使用的trie樹了，trie樹在不平衡的時候可以平衡化調整，可是OID樹能調整嗎？...

     下面的perl代碼展示了OID的編碼過程：

sub der_it

    {

    local($v)=@_;

    local(@a,$i,$ret,@r);

    @a=split(//s+/,$v);

    $ret.=pack("C*",$a[0]*40+$a[1]);

    shift @a;

    foreach (@a)

        {

        @r=();

        $t=0;

        while ($_ >= 128)

            {

            $x=$_%128;

            $_/=128;

            push(@r,((($t++)?0x80:0)|$x));

            }

        push(@r,((($t++)?0x80:0)|$_));

        $ret.=pack("C*",reverse(@r));

        }

    return($ret);

    }

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1271781