如何将整数编码为其他整数？

Question

作为的后续，我想知道是否有一个概括，您可以将 n 个 x 位数字存储到 m 个 y 位数字中。例如，也许您可以将 5 个 8 位数字存储为 3 个 15 位数字。或者可能将 2 个 8 位数字转换为 1 个 16 位数字，或者将 3 个 16 位数字转换为 2 个 32 位数字。想知道执行此操作的过程的编码和解码实现是什么，或者如果不可能。

类似于：

function encode(i, s1, n, s2) {
  // i = array of input bytes
  // s1 = size of input bytes
  // n = number of output bytes
  // s2 = size of output bytes
}

function decode(i, s1, n, s2) {

}

根据下面的答案，我尝试将其翻译成 JavaScript，但不明白任何东西的真正含义并且认为它不起作用。

function encode(input, inputSize, outputSize, callback) {
  var buffer = 0
  var bbits = 0
  var mask = (1 << outputSize) - 1
  while (bbits < outputSize) {
    buffer |= (input << bbits)
    bbits += inputSize
  }
  while (bbits >= outputSize) {
    callback(buffer & mask)
    buffer >>= outputSize
    bbits -= outputSize
  }
}

Answer 1

一般情况是 "streaming"，无论一切都严重错位，它都有效。像往常一样，它通过降低效率来换取通用性。它的工作原理基本上是将输入放入缓冲区，直到至少可以从中提取一次输出块，然后提取所有输出，所以像这样：

buffer = 0
bbits = 0
mask = (1 << outSize) - 1
while more input:
    while bbits < outSize:
        buffer |= in() << bbits
        bbits += inSize
    while bbits >= outSize:
        out(buffer & mask)
        buffer >>= outSize
        bbits -= outSize
if bbits != 0:
    out(buffer & mask)

编码和解码在概念上是相同的，但大小互换。当专用于特定大小的输入和输出块时，内部循环之一将不是循环。也可以使用其他打包顺序，在低位之前输出一大块输入的高位，随你喜欢。

缓冲区的大小必须至少outSize - 1 + inSize，以容纳从缓冲区输出后剩余的最大位数后的读取输入。

甚至可以在手术过程中更改尺寸。

Answer 2

您不能将 5 个 8 位数字存储到 3 个 15 位数字中，因为 45 位信息显然放不下 40 位内存。只有当变化总数小于或等于 2^k 时才能这样做，其中 k 是用于编码的位数

如果每个值的宽度都相同，那么这是我的尝试，它以大端方式线性存储位。 encode 函数将字节数组中的位转换为另一个数组，该数组将完整值存储在 bitLength 位中， decode 函数执行相反的操作

function encode(input, bitLength) {
  // size of each array element must be greater than bitLength
  var output = new Uint16Array(Math.ceil(input.length * 8 / bitLength));
  var remainingBits = bitLength; // the remaining bits left for the current value

  // example when bitLength = 11
  //       start of current value
  //       │          next value
  //       │2345678901│
  // ...┆  ↓    ┆     ↓ ┆       ┆       ┆       ┆...      ← input bytes
  // ...₀₁₂₃₄₅₆₇⁰¹²³⁴⁵⁶⁷₀₁₂₃₄₅₆₇⁰¹²³⁴⁵⁶⁷₀₁₂₃₄₅₆₇ ...      ← bit position

  for (var inIdx = 0, outIdx = 0; inIdx < input.length; inIdx++) {
    if (remainingBits > 8) {
      output[outIdx] = (output[outIdx] << 8) | input[inIdx];
      remainingBits -= 8;               // 8 less bits to read
    } else if (remainingBits == 8) {    // finish current value
      output[outIdx] = (output[outIdx] << 8) | input[inIdx];
      remainingBits = bitLength; // next byte is the start of the next output value
      outIdx++;
    } else {
      var nextRemainingBits = 8 - remainingBits;
      output[outIdx] = (output[outIdx] << remainingBits)
                     | (input[inIdx] >>> nextRemainingBits);
      // the leftover bits (nextRemainingBits) in the input byte
      // go into the next output
      output[++outIdx] = input[inIdx] & ((1 << nextRemainingBits) - 1);
      // adjust the number of remaining bits, after we've read
      // `8 - remainingBits` bits for the current output
      remainingBits = bitLength - nextRemainingBits;
    }
  }
  return output;
}

function decode(input, bitLength) {
    const numBits = input.BYTES_PER_ELEMENT*8;
  var output = new Uint8Array(Math.ceil(input.length * bitLength / 8));
  var remainingInputBits = bitLength; // the remaining bits left for the current value
  
  // shift value to the most significant position
  for (var i = 0; i < input.length; i++)
    input[i] <<= numBits - bitLength;
  
  for (var inIdx = 0, outIdx = 0; outIdx < output.length; outIdx++) {
    if (remainingInputBits > 8) {
      output[outIdx] = input[inIdx] >>> (numBits - 8);  // get the top byte from input
      input[inIdx] <<= 8;   // shift the read bits out, leaving next bits on top
      remainingInputBits -= 8;
    } else if (remainingInputBits == 8) {
      output[outIdx] = input[inIdx] >>> (numBits - 8);
      remainingInputBits = bitLength;
      inIdx++;
    } else {
      remainingInputBits = 8 - remainingInputBits;
      output[outIdx] = input[inIdx] >>> (numBits - 8);
      inIdx++;
      output[outIdx] |= input[inIdx] >>> (numBits - remainingInputBits);
      input[inIdx] <<= remainingInputBits;
      remainingInputBits = bitLength - remainingInputBits;
    }
  }
  return output;
}

function pad(s, size) {
  s = (s >>> 0).toString(2);
  while (s.length < (size || 2)) { s = "0" + s; }
  return s;
}

function printBinaryArray(arr, padLength) {
    var str = "";
    for (var i = 0; i < arr.length; i++)
        str += pad(arr[i], padLength) + " ";
    console.log(str);
}

var inputBytes = 22;
var bitLength = 11; // each value is 11-bit long
var input = new Uint8Array(inputBytes);

window.crypto.getRandomValues(input);

var encodedData = encode(input, bitLength);
console.log("Input data", input);
printBinaryArray(input, 8);
console.log("Encoded data");
// console.log(encodedData);
printBinaryArray(encodedData, bitLength);

var decodedData = decode(encodedData, bitLength);
console.log("Decoded data", decodedData);
printBinaryArray(decodedData, 8);

for (var i = 0; i < input.length; i++)
    if (input[i] != decodedData[i])
        console.log("Wrong decoded data");
console.log("Data decoded successfully");

其实编码和解码的过程只是互为逆序，所以你可以很容易的修改成encode(input, inputBitWidth, outputBitWidth)既可以编码也可以解码，只需要调换输入和输出的宽度

然而，对于奇数大小的值，通常最好将高位打包在一起以便于访问。例如10位像素格式通常将4个像素打包成一个5字节的组，每个像素的高8位在前4个字节，最后一个字节包含它们的2个低位

另见

anyone know 10-bit raw rgb? about omnivision
large array of 26-bit unsigned integers
packing 10 bit values into a byte stream with SIMD

如何将整数编码为其他整数？

How to encode integers into other integers?

encoding

integer

byte

bitstream