ASN.1的PER编码例子
为了解决高级语言中结构化数据在网络传输中的结构关系能送达目的地进行还原，历史上出现了以下几种数据序列化的方法：ASN.1，XML，Json等。
ASN.1本身只定义了表示信息的抽象句法，但是没有限定其编码的方法。各种ASN.1编码规则提供了由ASN.1描述其抽象句法的数据的值的传送语法（具体表达）。
标准的ASN.1编码规则有基本编码规则（BER，Basic Encoding Rules）、规范编码规则（CER，Canonical Encoding Rules）、唯一编码规则（DER，Distinguished Encoding Rules）、压缩编码规则（PER，Packed Encoding Rules）和XML编码规则（XER，XML Encoding Rules）。
下面主要介绍PER编码规则：
PER编码规则可以分为基本的（Basic）和规范的（Canonical）两类，每一类又可以分为对齐（Aligned）和不对齐（Unaligned）两种。
规范形式主要用在中继接力系统和安全系统等使用数字签名的场合。
在基本形式中，一个抽象值可能有多个PER编码。但是，在有限测试后，我们知道基本形式编码器要比规范形式编码器速度更快。
对齐方式下，为了保持八位组对齐，可以增加值为0的比特。
不对齐方式则编码更为紧凑，但是在编解码时需要花费更多的处理时间。不对齐方式下，不会检查八位组的对齐情况，只在整个数据编码结束后，才进行补位。
注意对齐和不对齐两种方式不能互通，即只能用同种的解码器解码同种编码器编码后的码流。
在四种变形中，基本不对齐方式编码是最紧凑的。
按照紧凑性降低的顺序，后续依次为：
规范不对齐方式，
基本对齐方式
规范对齐方式。
PER可见子类型约束
为了最大限度的压缩编码，PER需要依赖ASN.1描述中的子类型约束。约束增加的越具体，PER越能得到更优化的编码（压缩越多）。而且PER会使用到的约束都是经常使用的约束，这样也使得PER编译器容易实现。此外，这些约束都是编译器在编译过程中“静态”使用的，不会增加实际编解码过程处理时间。
我们称这类约束为PER可见约束（PER-Visible Constraints），它们只包含下表所列：
open types指引用到一个类型域、一个可变类型的值域、或者一个可变类型值集合域。即引用到信息对象类中的类型。
数的编码
自然数（非负数）的四种形式的编码，因为自然数常出现在长度域L、bitmap的大小、CHOICE中的序号以及INTEGER类型边界中。
对于INTEGER类型，PER可见约束之一是值域约束。对于有值域约束(bmin…bmax)的值n，如果下边界bmin足够大，PER编码n- bmin的代价就更小。如下：
I. 有约束数编码
有约束指值域的上、下边界都有限。设d为取值范围的大小（上下边界的差值）；
在对齐方式下：
l 当2≤d≤255，n- bmin的编码占用log2d个比特。这些比特添加在待发送比特域之后，不进行八位组对齐，不编码L；
l 当d=256，n- bmin的编码占用一个八位组，不编码L；
l 当257≤d≤65,536，n- bmin的编码占用两个八位组，不编码L；
l 当65,537≤d，n- bmin的编码占用log256d个八位组，并且在前面增加L的编码。
在不对齐方式下：
l n- bmin的编码占用log2d个比特，不编码L。
II. 半约束数编码
半约束指值域没有上边界（上边界为+∞）。
n- bmin的编码占用log256d个八位组，并且在前面增加L的编码。
III. 无约束数编码
无约束指值域没有下边界（即使存在上边界）。
按照BER中整数的编码方式编码，并且在前面增加L的编码。
IV. 常见小自然数编码
这种情况经常出现在对表征SEQUENCE、SET类型可选成员的Bitmap长度进行编码时；或者CHOICE类型序号编码时。这种长度相当小，但是却没有一种限定。
l 当0≤n≤63时，n以6个比特编码，并且在前面增加一个***0***比特（八位组不对齐）：
l 当64≤n时，n以半约束数方式编码，下边界为0，并且在前面增加一个***1***比特：
长度域编码
在PER的长度域出现下，
如果编码为比特串则表征比特位数；
如果编码为八位组串（OCTET STRING和open类型）则表征八位组个数；
如果编码为known-multiplier character string则表征字符数；
如果是SEQUENCE OF或者SET OF则表征成员个数。
每当ASN.1描述中 对类型通过(SIZE(lmin…lmax))做大小限定时（lmax可以是+∞），长度l的值要按照上面数的规则编码。作为特例，当lmin =lmax≤65,535时，长度不需要发送，因为解码器知道该长度。
对齐方式下：
l 当l是一个bitmap的长度，l-1作为常见小自然数编码；
l 当lmax≤65,535，l作为有约束的数编码（约束为(lmin…lmax)）；
l 当65,535≤lmax，或者lmax是无穷大：
－ 当l≤127，l以一个八位组编码（八位组对齐），最高比特位为0；
－当128≤l≤16,383，l以两个八位组编码（八位组对齐），最高两个比特位为10；
－当16,384≤l，整个编码以f*16K为单位分割（f取值为1，2，3或者4）。除最后的片段外，其余每段，长度都以一个八位组编码，最高两个比特位为11。如果编码恰好时16K的整倍数，则在最后补充一个全空的八位组；否则最后一个片段按照前两条进行编码。例如占147,457个单元的编码可以为：
不对齐方式下：
l 当l是一个bitmap的长度，l-1作为常见小自然数编码；
l 当lmax≤65,535，l-lmin以占用log2(lmin-lmax+1)个比特编码；
l 当65,534≤lmax-lmin，或者上边界为无穷大：
－当l≤127，l以八比特编码，最高比特位为0；
－当128≤l≤16,383，l以十六比特编码，最高两个比特位为10；
－当16,384≤l，编码方式域对齐类似，但是不是八位组对齐的。
当类型有可扩展的SIZE约束，并且待发送值不在该约束扩展的根部分，则长度l作为半约束数编码（即lmin=0， lmax =+∞）
各类型的编码方式：
1 BOOLEAN
以一个比特编码，1为TRUE，0为FLASE。
2 NULL
不编码
3 INTEGER
假设INTEGER类型拥有有效的值域范围(bmin…bmax)，当描述中INTEGER类型有至少一个可扩展的PER可见约束（PER-Visible Constraint），在编码时会在前面增加一个前导（Preamble）比特（不考虑八位组是否对齐）。当INTEGER类型的值在扩展的根部分，该比特为0；否则该比特为1。
在编码n- bmin过程中，如果需要编码L（前面讨论过），则增加长度域L的编码。长度L的约束为(1…lmax)，其中lmax =log2bmax。
如果待发送值n属于约束的扩展部分，则长度按照无约束自然数方式编码，
4 ENUMERATED
如果该ENUMERATED类型不是可扩展的，则先按照数值大小做升序排列，然后以0为起点，步长为1给每个成员编上序号。对该类型的值编码时，只将序号以值域约束(0…Indexmax)编码。如：
v ENUMERATED {orange(56), green(-2), red(2476)} ::= orange
的PER编码为“01”（因为此时为Indexmax 2，需要两个比特）。
如果该ENUMERATED类型是可扩展的，那么要在编码前增加一个前导（Preamble）比特。当值在扩展的根部分时，该比特为0；否则该比特为1。同时对扩展部分的成员重新进行编号，起点仍为0，步长为1。编码时对值在根部分的情况，就和该类型是不可扩展时一样；值在扩展部分的情况，对序号按照自然数方式编码。如：
v1 ENUMERATED {orange(56), green(-2), red(2476), …, yellow}
::= orange
的PER编码仍然为“01”；而
v2 ENUMERATED {orange(56), green(-2), red(2476), …, yellow, purple}
::= yellow
的PER编码则为“10000000”。
.5 REAL
对值的编码规则和CER或者DER相同（而且是八位组对齐的），并且在前面增加长度域L的编码。这里L表征的是八位组数。
VI. BIT STRING
如果该BIT STRING类型有可扩展的PER可见大小约束（PER-Visible Size Constraint），那么要在编码前增加一个前导（Preamble）比特。当值在扩展的根部分时，该比特为0；否则该比特为1。
对于有大小约束(SIZE(lmin…lmax))的BIT STRING类型：
l 当lmin＝lmax≤16比特，不发送长度，直接编码（不是八位组对齐的）；
l 当17≤lmin＝lmax≤65,536比特，不发送长度，直接编码（在八位组对齐方式下是八位组对齐的）；
l 当65,537≤lmin＝lmax，长度按照3.3.5 中约定编码；而值按照需要进行分段；
l 当lmin≠lmax（或者没有有效的大小约束），长度按照3.3.5 中约定编码；而值按照需要进行分段。
如果BIT STRING类型包含一个命名位置列表，所有结尾的0比特都被去掉；此外，为了满足大小约束，可以增加或者删除结尾0比特来达到最小的长度。
VII. OCTET STRING
与BIT STRING规则相同，不过长度域L表征的是八位组的个数而不是比特数。
VIII. OBJECT IDENTIFIER
值的编码规则与BER相同，前面需要增加长度域L的编码。
IX. RELATIVE-OID
值的编码规则与BER相同，前面需要增加长度域L的编码。
X. 字符串与日期
首先描述known-multiplier字符串类型，如果这种类型是受约束的，带了一个形如（SIZE(lmin , lmax)）的有效的size约束和一个形如（FROM(“c1”|“c2”|…|“cn”)）的有效的字符约束。如果FROM约束是可扩展的，则有效的字符约束就包括了父类型包含的所有的字符。
如果SIZE约束是可扩展的，则在bit-field上加一个比特。如果串长属于扩展根的范围内，则该比特等于0，否则该比特等于1。记住，如果FROM约束中包含了可扩展的符号，则该约束对于PER不可见，即不会改变扩展比特的取值。
PER压缩known-multiplier字符串类是基于有效的字符约束的。假设n是有效字符约束中字符的个数，b ＝ [log2 n], c = [log2 b],则每个字符在aligned变体中被编码成B = 2 c个比特（大于b的最小的2的次方），而在unaligned变体中被编码成B = b 个比特。设vmin 和vmax 分别是(“c1”|“c2”|…|“cn”)对应的最小和最大的字符值。
如果vmax≤ 2B -1, 即所有的系列里的(“c1”|“c2”|…|“cn”)都可以用B个比特来编码，串中的每个字符都可以作为在区间(vmin … vmax)之间的一个整数来编码。这就避免了给字符重新排序赋值。否则，字符序列(“c1”|“c2”|…|“cn”)按照标准[ISO646] 或 [ISO10646-1]中定义的顺序加索引，索引从0开始，每次加1。这个新的索引号以B个比特来编码和发送。
如果字符串的长度是固定的(lmin = lmax)并且小于64K，则长度字段L就不需要了，在aligned变体情况下，只有当 B ×lmax ≥ 17 时才需要octet - aligned。.
如果字符串的长度不固定或者长度虽然固定但大于64K，则长度字段按照章节3.2 编码，然后附着到码流中（在在aligned变体情况下，只有当 B ×lmax ≥ 17 时才需octet - aligned）。
例如，字符串
v IA5String (FROM (“ACGT”)^SIZE(3)) ::= “TAG”
被编码成 11 00 10 。而字符串
v IA5String ::= “TAG”
在unaligned变体情况下被编成（注：IA5String的vmin 和vmax分别为0和127）：
在aligned变体情况下被编成（下面的方框表示从整数个字节开始）
日期类型 GerneralizedTime和UTCTime 的编码方式在basic PER情况下与BER相同，在canonical PER情况下与DER相同。
对于不属于known-multiplier的字符串类型，所有的约束对PER都是不可见的。它们的编码方式在basic PER情况下与BER相同，在canonical PER情况下与DER相同。长度字段L作为一个无约束整数加在前面。
XI. Open类型
一个open类型的值实际上是一个任意类型的值，这个类型对于发送方和接收方而言都是已知的。因此这个值就被编成它的有效类型而没有类型的指示。通常情况下，这个值的类型已经在前面发送过了，解码器会存储类型到关联表中，而后在收到open类型能够的值后根据关联表就可以查询到对应的类型进行解码。
相应的值编码后，不是整数个字节的情况补充值为’0’的比特位以便使该码流为整数个字节（假设为n）。并在头部加上长度字段L表示字节数n，L作为无约束整数进行编码。
XII. SEQUENCE
首先，如果有COMPONENTS OF语句，则由相应的类型进行替换。
如果SEQUENCE类型是可扩展的，则在编码的头部加上一个比特的bit-field，如果SEQUENCE的取值中有属于扩展附加部分的成员，则该比特等于1，否则等于0。
如果SEQUENCE的定义中在扩展根部（extension root）有"n"个成员被置为OPTIONAL或DEFAULT，则在编码头部再添加"n"个比特的bit-field，该bit-field从第一个bit开始，依次指示被标记为OPTIONAL或DEFAULT的成员是否出现。如果为1，则该成员出现，否则没有出现。如果“n”小于64K，则这个 bit-field 应该直接添到码流中。如果"n"大于等于64K，按照前面提到的处理方法把“n”个bit的bit-field分段并添加到域序列中，前面的长度字段L就作为一个有约束的整数编码，而约束的上限和下限都等于n。
以上为导言（preamble）部分，导言之后是各成员类型的编码，依次出现。
在canonical PER中，对于标记有DEFAULT的成员，如果要编码的值就是缺省值，那么这个成员的编码省略；在basic PER中，如果序列中标记为DEFAULT的成员是一个简单类型，当它的值为缺省值时，它的编码应省略。而对于结构化的成员(SEQUENCE, SET, SEQUENCE OF, SET OF, CHOICE) ，即使它的取值是缺省值时，是否被编码是由发送方来决定的。
如果类型是可扩展的但取值中没有出现扩展附加部分，则该SEQUENCE的值的编码已经结束。
如果类型是可扩展的并且取值中有p个扩展附加部分（双重方括号内的所有成员只当作一个附加扩展部分），则添加一个p个比特的bit-map，对应的比特取值为1则表示该扩展附加部分出现，否则就没有出现。为长度"p"的bit-map增加一个长度指示，编码方式为一个通常的小的非负整数的编码。
以后，依次出现的是各扩展附加部分的编码值。
扩展附加部分的编码方式如下：
l 如果该扩展附加部分是单个的成员，则作为open类型来编码，即包括长度字段和整数个字节的值字段。
l 如果该扩展附加部分是由双重方括号内的所有成员组成的，则该扩展附加部分的值作为open类型来编码。与上面不同的是：双重方括号内的所有成员的值被当成一个SEQUENCE类型的取值来编码，编码方式参见本节上段。
注意在SEQUENCE类型的值没有包括长度字段，因为根据扩展根部的可选成员对应的bit-map和扩展附加部分对应的bit-map使解码器推断出成员是否存在。
XIII. SET
SET类型的扩展根部（extension root）的成员是按照canonical order来排序的，具体法则如下：
-
首先按标签类型排序，按照UNIVERSAL，APPLICATION，context-specific，PRIVATE四种类型依次排序，UNIVERSAL标签类型的元素在最前，PRIVATE标签类型的元素在最后； -
在标签类型内部，按照标签值的大小排序，小的在前，大的在后。
在排序过程中如果发现某个成员是没有标签的CHOICE类型，则该CHOICE类型的标签值就会等于其所有选项中标签的最小值。在CHOICE类型嵌套的情况下亦是如此。
如果SET类型是可扩展的且SET类型的值中有扩展附加部分，则扩展附加部分的排序按照其协议定义时的顺序，不做改动（因为在新增扩展附加部分时对应的标签必须符合canonical order）。
经过上述的排序后，SET类型的编码就按照SEQUENCE类型的编码。
XIV. SEQUENCE OF
显式PER限制仅仅对SEQUENCE OF类型的成员个数有效。
假设成员数目的上限为"ub"，下限为"lb"。如果没有上限或者上限值ub大于等于64K，就认为ub不确定；如果没有下限，"lb"置为0。假设实际的SEQUENCE OF的成员数量为“n”，编码按如下规则进行：
-
如果有size约束且该约束可扩展，则在码流上添加一个1比特的bit-field（不需要octet-aligned）。 如果元素的个数属于约束的根部则这个比特等于0，反之该比特等于1。在前一种情况下，调用节3.2为生成的编码增加一个半约束数的长度指示，长度值等于n。 -
如果成员值的数目固定且小于64K，则没有长度指示，SEQUENCE OF的各成员的值的编码依次填充到生成的编码中去。 -
其它情况，增加长度指示成员值的数目。如果"ub"存在，则长度指示作为约束数编码，否则作为半约束数类型的整数编码。
需要注意的是在给每个成员编码时，在aligned变体情况下需要octet-aligned。
XV. SET OF
在basic variant情况下，把每个SET类型的元素按顺序编码即可，而不需要调换顺序。而在canonical variant情况下需要先把各SET中的元素按canonical order进行排序再编码，并在必要的时候需要做一些调整，如加上一些’0’ bit以形成整数个字节，或加上值为0的字节以使短部分和长的部分长度一致。
XVI. CHOICE
先给CHOICE的各个选项标上索引（index），过程如下：
-
对于CHOICE类型的根部（root）的选项，先按照canonical order对各选项进行排序，然后给排序后的选项标上索引，第一个选择项索引为0，第二个为1，直至根部的最后一个。 如果嵌套了没有标签的CHOICE类型，则该类型的标签是其择项中的最小的那个标签。 -
如果CHOICE类型是可扩展的，并且有扩展附加选项，则给扩展附加选项也分别标上索引，第一个扩展附加选项的索引为0，第二个为1，直至扩展部分的最后一个。（标索引之前不需要对这些选项进行排序，是因为在新增扩展附加选项时对应的标签必须符合canonical order）。
在索引标完后，就可以对CHOICE类型的值进行编码，过程如下：
-
如果仅有一个选择项，如果选择了该选择项的话，不要对索引进行编码。 -
如果CHOICE类型是可扩展的，则在码流上加一个比特的bit-field（不需要octet-aligned）。如果该值属于扩展附加选项，则 该比特等于1，否则等于0。 -
如果没有扩展标记，或者有扩展标记但选项在CHOICE类型的根部，则选项的索引值就作为一个INTEGER来编码（约束为0..n，假设n为根部的最大索引值），然后是选项的值的编码。 -
如果有扩展标记且选项是CHOICE类型的扩展附加选项，则该索引被当作一个通常的小的非负整数进行编码，其"lb"置为0。把选项的值当作open类型进行编码。
XVII. Tagged Type
因为PER不是隐式支持Tag的，所以一个有Tag类型的值按照该类型的编码规则进行编码。在ASN.1模块内，特定Tag上的限制要遵守；建议在模块头的声明中增加AUTOMATIC TAGS，这不会影响已有的限制。
XVIII. EXTERNAL
略。
XIX. INSTANCE OF
一个INSTANCE OF类型的值按照其等效SEQUENCE类型值进行编码。
XX. EMBEDDED PDV或者CHARACTER STRING
如果EMBEDDED PDV或者CHARACTER STRING类型有WITH COMPONENTS约束，该约束限制可选项syntaxes是两个预定义object identifier的序列（即对收、发双方抽象语法、传输语法都明确）；或者限制成员identification选项为fixed，则PER编码中嵌入数据作为OCTET STRING类型编码。
如果成员identification没有按照前面两种方式之一约束，则这两种类型的值需要按照等效的SEQUENCE类型值进行编码。
XXI. Value Set
编码一个有值域Value Set约束类型的值时，值域被当作有该值域约束的类型看待。如值域：
Set1 INTEGER(1…20) ::= {1 | 5 | 7}
被等同作：
Set1 ::= INTEGER(1…20)(1|5|7)
XXII. Information Objects 与 Information Object Sets
信息对象和信息对象集合不编码。传输其中信息的方式，是在类型或者值中引用信息对象或者信息对象集合。编码时，按照所在值的编码规则进行编码。
实际编码例子：
PER对齐方式（一般RRC消息采用非对齐方式）：
NGAP的 NGSetUp消息的编码：
GlobalRANNodeID ::= CHOICE {
globalGNB-ID GlobalGNB-ID,
globalNgENB-ID GlobalNgENB-ID,
globalN3IWF-ID GlobalN3IWF-ID,
choice-Extensions ProtocolIE-SingleContainer { {GlobalRANNodeID-ExtIEs} }
}
GlobalGNB-ID ::= SEQUENCE {
pLMNIdentity PLMNIdentity,
gNB-ID GNB-ID,
iE-Extensions ProtocolExtensionContainer { {GlobalGNB-ID-ExtIEs} } OPTIONAL,
…
}
GNB-ID ::= CHOICE {
gNB-ID BIT STRING (SIZE(22…32)),
choice-Extensions ProtocolIE-SingleContainer { {GNB-ID-ExtIEs} }
}
上一篇： 排序算法之堆排序