2

作为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
  }
}
4

2 回答 2

3

您不能将 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 字节组，前 4 个字节中每个像素的 8 个高位，最后一个字节包含它们的 2 个低位

也可以看看

于 2019-03-16T15:57:11.053 回答
2

一般情况是“流式传输”，无论所有内容的错位有多么严重，它都能正常工作。像往常一样，它通过降低效率来为一般性付出代价。它的工作原理是将输入放入缓冲区，直到可以从中提取至少一次输出块，然后提取所有输出，因此如下所示：

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，以适应从缓冲区输出后剩余最大位数后的读取输入。

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

于 2018-07-07T22:26:34.377 回答