复盘 - 华为机试 - TLV编码解析

原题

TLV编码是按照[Tag Length Value]格式进行编码的,一段码流中的信元用Tag标识,Tag在码流中唯一不重复。Length表示信元的Value长度,Value表示信元的值。码流以某信元的Tag开头,Tag固定一个字节,Length固定占满两个字节,字节序统一为小端序。

现给定一个TLV格式编码的码流,以及需要解码的信元Tag,请输出该信元的Value。输入码流的16进制字符中,不包含小写字母,且要求输出的16进制字符串中也不要包含小写字母;码流字符串的最大长度不超过50000个字节。

输入描述:

  • 输入的第一行为一个字符串,表示需解码信元的Tag;
  • 输入的第二行为一个字符串,表示需解码的16进制码流,字符间用空格分隔。

输出描述:

  • 输出一个字符串,表示待解码信元Tag对应的十六进制表示的value。

示例

输入

31
32 01 00 AE 90 02 00 01 02 30 03 00 AB 32 31 31 02 00 32 33 33 01 00 CC

输出

32 33

大白话解释

TLV字符串的格式为:“tag”+“length”+“value” + “tag”+“length”+“value” + “tag”+“length”+“value” …

其中tag的长度为1字节,length的长度为2字节,value的长度取决于length的值。

第一行输入要解析的tag,第二行输入一个TLV字符串。需要解析出TLV字符串中对应tag的value,并将value输出

考点

小端字节序和大端字节序的区别,以及十六进制的处理

例如:16进制字符串0C 6F 代表长度为两字节,以小端序读取为6F0C,大端序读取为0C6F

思路

31
32 01 00 AE 90 02 00 01 02 30 03 00 AB 32 31 31 02 00 32 33 33 01 00 CC
  1. 从字符串的第一个字节开始,第一个字节代表tag,即十六进制的32,接着后面是length,值为01 00,以小端序读取值为1,所以第一段TLV的value是AE
  2. 第二段,tag为90,length是02 00,即长度为2,value是01 02,解读出来是02 01.
  3. 第三段,tag为30,length是03 00,即长度为3,value是AB 32 31,解读出来是31 32 AB.
  4. 第四段,tag为31,length是02 00,即长度为2,value是32 33,解读出来是33 32.
  5. 第四段解析成功,tag满足第一行输入的tag,匹配成功,输出value32 33.

实现

  1. 将一段16进制的字符串使用 ArrayBufferuint8Array(视图数组)构造函数,将十六进制字符串按照一个字节一个字节的拆分,得到一个新数组,并循环操作这个数组。

    关于ArrayBuffer,我以前专门研究过,并在B站上传了学习视频:B站链接,40分钟超详细解析,有时间的话可以看一看。

  2. 解析出每一段的tag、length和value,找到与第一行输入匹配的tag,并输入出其对应的value即可。

演示代码,不代表最佳性能:

// 将16进制字符串转换为TypedArray字节串
function hexToBytes(hex) {
  const hexStr = hex.replace(/ /g, ""); // 去除间隔的字符串
  const bytesLength = hexStr.length / 2; // 16进制字符串以两个字母为1字节,除以2得到字节长度
  const bytes = new Uint8Array(bytesLength); // 得到一个TypedArray数组,数组的一个元素就是一个字节

  /**
   * bytes是一个特殊的数组,我们可以像操作内存一样直接去修改某一个字节的数据。
   * 需要注意的是,TypedArray会自动将16进制转为10进制,所以bytes存储的是TLV字符串的十进制版本
   */
  const hexArr = hex.split(" ");
  for (let i = 0; i < bytesLength; i++) {
    bytes[i] = parseInt(hexArr[i], 16);
  }

  return bytes;
}

// 对hex的TypedArray进行解析
function parseTLV(hexBytes, targetTag) {
  let result = []; // 存储结果的数组
  let index = 0;
  while (index < hexBytes.length) {
    // 得到当前TLV的tag
    const tag = hexBytes[index];

    // 得到当前TLV的length
    const length = hexBytes[index + 1] | (hexBytes[index + 2] << 8);

    // 得到当前TLV的value
    const value = hexBytes.slice(index + 3, index + 3 + length);

    // 使用toString方法将10进制转为16进制,如果跟目标的tag匹配就结束循环,返回结果
    if (targetTag == tag.toString(16)) {
      const newTag = tag.toString(16).toUpperCase().padStart(2, "0");
      // value是一个TypedArray,会将字节转成10进制整数,所以转换为16进制,并全部转成大写
      // 尤其是16进制的英文字母需要特别注意,未满2位的需要在前面填充0
      const newValue = Array.from(value, item => item.toString(16).toUpperCase().padStart(2, "0"));

      result = [newTag, newValue];
      break;
    }

    index += 3 + length;
  }
  return result;
}

// 解析TLV
function decodeTLV(tag, hex) {
  const hexBytes = hexToBytes(hex);

  const result = parseTLV(hexBytes, tag); // 解析TLV字符串
  console.log("result: ", result[0], result[1]);

  return result[1].join(" ");
}

// 原题示例
const tag = "33";
const hexStream = "32 01 00 AE 90 02 00 01 02 30 03 00 AB 32 31 31 02 00 32 33 33 01 00 CC";
console.log(decodeTLV(tag, hexStream));
4 Likes

这是两年前做的,给大家看个乐呵

#JS添加

:+1:牛的

大帅哥真是无处不在啊

我夸你厉害,你怎么这么说我

好的,大帅哥

From #dev to 开发调优