ceph/src/arrow/js/src/util/bit.ts

   1 // Licensed to the Apache Software Foundation (ASF) under one
   2 // or more contributor license agreements.  See the NOTICE file
   3 // distributed with this work for additional information
   4 // regarding copyright ownership.  The ASF licenses this file
   5 // to you under the Apache License, Version 2.0 (the
   6 // "License"); you may not use this file except in compliance
   7 // with the License.  You may obtain a copy of the License at
   8 //
   9 //   http://www.apache.org/licenses/LICENSE-2.0
  10 //
  11 // Unless required by applicable law or agreed to in writing,
  12 // software distributed under the License is distributed on an
  13 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14 // KIND, either express or implied.  See the License for the
  15 // specific language governing permissions and limitations
  16 // under the License.
  17
  18 /** @ignore */
  19 export function getBool(_data: any, _index: number, byte: number, bit: number) {
  20     return (byte & 1 << bit) !== 0;
  21 }
  22
  23 /** @ignore */
  24 export function getBit(_data: any, _index: number, byte: number, bit: number): 0 | 1 {
  25     return (byte & 1 << bit) >> bit as (0 | 1);
  26 }
  27
  28 /** @ignore */
  29 export function setBool(bytes: Uint8Array, index: number, value: any) {
  30     return value ?
  31         !!(bytes[index >> 3] |=  (1 << (index % 8))) || true :
  32         !(bytes[index >> 3] &= ~(1 << (index % 8))) && false ;
  33 }
  34
  35 /** @ignore */
  36 export function truncateBitmap(offset: number, length: number, bitmap: Uint8Array) {
  37     const alignedSize = (bitmap.byteLength + 7) & ~7;
  38     if (offset > 0 || bitmap.byteLength < alignedSize) {
  39         const bytes = new Uint8Array(alignedSize);
  40         // If the offset is a multiple of 8 bits, it's safe to slice the bitmap
  41         bytes.set(offset % 8 === 0 ? bitmap.subarray(offset >> 3) :
  42             // Otherwise iterate each bit from the offset and return a new one
  43             packBools(new BitIterator(bitmap, offset, length, null, getBool)).subarray(0, alignedSize));
  44         return bytes;
  45     }
  46     return bitmap;
  47 }
  48
  49 /** @ignore */
  50 export function packBools(values: Iterable<any>) {
  51     const xs: number[] = [];
  52     let i = 0, bit = 0, byte = 0;
  53     for (const value of values) {
  54         value && (byte |= 1 << bit);
  55         if (++bit === 8) {
  56             xs[i++] = byte;
  57             byte = bit = 0;
  58         }
  59     }
  60     if (i === 0 || bit > 0) { xs[i++] = byte; }
  61     const b = new Uint8Array((xs.length + 7) & ~7);
  62     b.set(xs);
  63     return b;
  64 }
  65
  66 /** @ignore */
  67 export class BitIterator<T> implements IterableIterator<T> {
  68     bit: number;
  69     byte: number;
  70     byteIndex: number;
  71     index: number;
  72
  73     constructor(
  74         private bytes: Uint8Array,
  75         begin: number,
  76         private length: number,
  77         private context: any,
  78         private get: (context: any, index: number, byte: number, bit: number) => T
  79     ) {
  80         this.bit = begin % 8;
  81         this.byteIndex = begin >> 3;
  82         this.byte = bytes[this.byteIndex++];
  83         this.index = 0;
  84     }
  85
  86     next(): IteratorResult<T> {
  87         if (this.index < this.length) {
  88             if (this.bit === 8) {
  89                 this.bit = 0;
  90                 this.byte = this.bytes[this.byteIndex++];
  91             }
  92             return {
  93                 value: this.get(this.context, this.index++, this.byte, this.bit++)
  94             };
  95         }
  96         return { done: true, value: null };
  97     }
  98
  99     [Symbol.iterator]() {
 100         return this;
 101     }
 102 }
 103
 104 /**
 105  * Compute the population count (the number of bits set to 1) for a range of bits in a Uint8Array.
 106  * @param vector The Uint8Array of bits for which to compute the population count.
 107  * @param lhs The range's left-hand side (or start) bit
 108  * @param rhs The range's right-hand side (or end) bit
 109  */
 110 /** @ignore */
 111 export function popcnt_bit_range(data: Uint8Array, lhs: number, rhs: number): number {
 112     if (rhs - lhs <= 0) { return 0; }
 113     // If the bit range is less than one byte, sum the 1 bits in the bit range
 114     if (rhs - lhs < 8) {
 115         let sum = 0;
 116         for (const bit of new BitIterator(data, lhs, rhs - lhs, data, getBit)) {
 117             sum += bit;
 118         }
 119         return sum;
 120     }
 121     // Get the next lowest multiple of 8 from the right hand side
 122     const rhsInside = rhs >> 3 << 3;
 123     // Get the next highest multiple of 8 from the left hand side
 124     const lhsInside = lhs + (lhs % 8 === 0 ? 0 : 8 - lhs % 8);
 125     return (
 126         // Get the popcnt of bits between the left hand side, and the next highest multiple of 8
 127         popcnt_bit_range(data, lhs, lhsInside) +
 128         // Get the popcnt of bits between the right hand side, and the next lowest multiple of 8
 129         popcnt_bit_range(data, rhsInside, rhs) +
 130         // Get the popcnt of all bits between the left and right hand sides' multiples of 8
 131         popcnt_array(data, lhsInside >> 3, (rhsInside - lhsInside) >> 3)
 132     );
 133 }
 134
 135 /** @ignore */
 136 export function popcnt_array(arr: ArrayBufferView, byteOffset?: number, byteLength?: number) {
 137     let cnt = 0, pos = byteOffset! | 0;
 138     const view = new DataView(arr.buffer, arr.byteOffset, arr.byteLength);
 139     const len =  byteLength === void 0 ? arr.byteLength : pos + byteLength;
 140     while (len - pos >= 4) {
 141         cnt += popcnt_uint32(view.getUint32(pos));
 142         pos += 4;
 143     }
 144     while (len - pos >= 2) {
 145         cnt += popcnt_uint32(view.getUint16(pos));
 146         pos += 2;
 147     }
 148     while (len - pos >= 1) {
 149         cnt += popcnt_uint32(view.getUint8(pos));
 150         pos += 1;
 151     }
 152     return cnt;
 153 }
 154
 155 /** @ignore */
 156 export function popcnt_uint32(uint32: number): number {
 157     let i = uint32 | 0;
 158     i = i - ((i >>> 1) & 0x55555555);
 159     i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 160     return (((i + (i >>> 4)) & 0x0F0F0F0F) * 0x01010101) >>> 24;
 161 }