时间戳

首页 > 解决方案 > 如何在 PHP 中解码 varints 的特定字节字符串

php - 如何在 PHP 中解码 varints 的特定字节字符串

问题描述

我正在尝试使用 PHP 以特定格式（炉石牌组代码）解码字符串，如下所示：

AAEBAc2xAgjAAe0E7QX3DdYRh6wC8fsCoIADC8kDqwTLBPsMhRDH0wKW6AK0/ALNiQPXiQOfmwMA

或者

AAEBAf0GBAD6DoyAA6CAAw37AZwCigbJB/gHlA+CEIUQrRDy0AL2/QKJgAPRgAMA

规格（原始描述）是：

数据字符串是一个 -encodedbase64字节字符串。

除非另有说明，否则后面的每个值都是一个整数，编码为unsigned varint.

  1. 标题块

    • 保留字节 0x00
    • 版本 (1)
    • 格式

  2. 数据块
    数据块被分成四对长度+数组，顺序如下：

    • 英雄
    • 单张卡
    • 2张卡片
    • n 副本卡

每对都有一个前导varint指定数组中的项目数。对于前三个块，它们是varints. 对于最后一个块，它是成对的数组varints。这种结构的目标是使数据串尽可能紧凑。

我已经开始把一些东西放在一起，但是在处理原始字节时我是个新手。我的代码是：

    // I found this to decode Variable-length quantity (varint)
    function vlq_decode(array $bytes) {
        $result = [];
        $integer = 0;
        foreach ($bytes as $byte) {
            if ($integer > 0xfffffff - 0x7f) {
                throw new OverflowException('The value exceeds the maximum allowed.');
            }
            $integer <<= 7;
            $integer |= 0x7f & $byte;

            if (($byte & 0x80) === 0) {
                $result[] = $integer;
                $integer = 0;
            }
        }
        if (($byte & 0x80) !== 0) {
            throw new InvalidArgumentException('Incomplete byte sequence.');
        }
        return $result;
    }

    $datastring = 'AAEBAc2xAgjAAe0E7QX3DdYRh6wC8fsCoIADC8kDqwTLBPsMhRDH0wKW6AK0/ALNiQPXiQOfmwMA';

    $raw = base64_decode($datastring);

    $byte_array = unpack('C*', $raw);

    $result = vlq_decode($byte_array);

    print_r($result);

我唯一确定的是base64_decode。我不知道unpack参数是否正确，或者vlq_decode函数是否按预期工作，因为我没有自己写。

在原始站点上有 Python 和 Javascript 的参考实现，但它们超出了我的想象，我无法使用这些代码来完成我的工作。

更新：

该代码确实产生了一个array看起来与我期望的相似的值，但许多值似乎并不正确。我认为从的转换varint仍然有些偏离。

// this is the $result I get (wrong)
Array (
    [0] => 0 // this is always 0
    [1] => 1 // Version
    [2] => 1 // Format
    [3] => 1 // What follows is an array of length 1 (data block Heroes)
    [4] => 1267842
    [5] => 8 // What follows is an array of length 8 (data block single-copy cards)
    [6] => 8193
    [7] => 13956
    [8] => 13957
    [9] => 15245
    [10] => 11025
    [11] => 120322
    [12] => 1867138
    [13] => 524291
    [14] => 11 // What follows is an array of length 11 (data block 2-copy cards)
    [15] => 9347
    [16] => 5508
    [17] => 9604
    [18] => 15756
    [19] => 656
    [20] => 1173890
    [21] => 373762
    [22] => 867842
    [23] => 1262723
    [24] => 1426563
    [25] => 511363
    [26] => 0  // What follows is an array of length 0 (data block n-copy cards)
)

Python 实现 ( Gist ) 生成不同的数字，格式略有不同，与包含 ID 数据的数据库（在dbfId字段中）很好地匹配

// this is the expected (correct) $result
Array (
    [0] => 0
    [1] => 1
    [2] => 1
    [3] => 1
    [4] => 39117
    [5] => 8
    [6] => 192 
    [7] => 621 
    [8] => 749 
    [9] => 1783 
    [10] => 2262 
    [11] => 38407 
    [12] => 48625 
    [13] => 49184 
    [14] => 11
    [15] => 457 
    [16] => 555 
    [17] => 587 
    [18] => 1659 
    [19] => 2053 
    [20] => 43463 
    [21] => 46102 
    [22] => 48692 
    [23] => 50381 
    [24] => 50391 
    [25] => 52639
    [26] => 0
)

任何帮助表示赞赏！

已经有一个关于这个主题的问题，但它写得很糟糕，没有代码示例，所以我再试一次。

标签： phpdecodingvarint

解决方案

这是一个字节序问题，也就是您需要以相反的顺序从每个 varint 字节中推送位。线索是低于 128 的值使其不受干扰。

下面是一个说明性的 hack，不应在实际代码中使用：

str_split(decbin(1267842),7)

产量：

array(3) {
  [0]=>
  string(7) "1001101"
  [1]=>
  string(7) "0110001"
  [2]=>
  string(7) "0000010"
}

超级方便，它已经是 7 位的倍数，但可能也是字节序问题的症状。

反转，内爆，转换回来：

bindec(implode('', array_reverse(str_split(decbin(1267842),7))))

产量：

int(39117)

我重新调整了该功能以解决此问题：

function vlq_decode(array $bytes, $swap_endian=false) {
    $result = [];
    $segments = [];
    foreach ($bytes as $byte) {
        if( $swap_endian ) {
            array_unshift($segments, 0x7f & $byte);
        } else {
            $segments[] = ( 0x7f & $byte );
        }

        if (($byte & 0x80) === 0) {
            $integer = 0;
            foreach($segments as $segment) {
                $integer <<= 7;
                $integer |= ( 0x7f & $segment );
            }
            $result[] = $integer;
            $segments = [];
        }
    }
    if (($byte & 0x80) !== 0) {
        throw new InvalidArgumentException('Incomplete byte sequence.');
    }
    return $result;
}

然后vlq_decode($byte_array, true);会给你你想要的。

我删减了铺位溢出代码，因为它实际上永远不会检测到实际的溢出代码，并且还会使您陷入 32 位整数。如果您确实想在解码过程中检测到溢出，则需要计算要解包的位，这只是一个麻烦：P

推荐阅读