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

Question

作为 Store 2 4-bit numbers in 1 8 bit number 的后续行动，我想知道是否有一个概括，您可以将 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

您无法将 5 个 8 位数字存储为 3 个 15 位数字，因为 45 位信息显然无法容纳在 40 位内存中。仅当变体总数小于或等于 2^k 时才可以执行此操作，其中 k 是用于编码的位数

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

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 个低位

另请参阅

• Extract 14-bit values from an array of bytes in C
• 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