bitmap_generate.go

Documentation: github.com/apache/arrow/go/v15/internal/bitutils

     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, software
    12  // distributed under the License is distributed on an "AS IS" BASIS,
    13  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14  // See the License for the specific language governing permissions and
    15  // limitations under the License.
    16  
    17  package bitutils
    18  
    19  import "github.com/apache/arrow/go/v15/arrow/bitutil"
    20  
    21  // GenerateBits writes sequential bits to a bitmap. Bits preceding the
    22  // initial start offset are preserved, bits following the bitmap may
    23  // get clobbered.
    24  func GenerateBits(bitmap []byte, start, length int64, g func() bool) {
    25  	if length == 0 {
    26  		return
    27  	}
    28  
    29  	cur := bitmap[start/8:]
    30  	mask := bitutil.BitMask[start%8]
    31  	curbyte := cur[0] & bitutil.PrecedingBitmask[start%8]
    32  
    33  	for i := int64(0); i < length; i++ {
    34  		bit := g()
    35  		if bit {
    36  			curbyte = curbyte | mask
    37  		}
    38  		mask <<= 1
    39  		if mask == 0 {
    40  			mask = 1
    41  			cur[0] = curbyte
    42  			cur = cur[1:]
    43  			curbyte = 0
    44  		}
    45  	}
    46  
    47  	if mask != 1 {
    48  		cur[0] = curbyte
    49  	}
    50  }
    51  
    52  // GenerateBitsUnrolled is like GenerateBits but unrolls its main loop for
    53  // higher performance.
    54  //
    55  // See the benchmarks for evidence.
    56  func GenerateBitsUnrolled(bitmap []byte, start, length int64, g func() bool) {
    57  	if length == 0 {
    58  		return
    59  	}
    60  
    61  	var (
    62  		curbyte        byte
    63  		cur                   = bitmap[start/8:]
    64  		startBitOffset uint64 = uint64(start % 8)
    65  		mask                  = bitutil.BitMask[startBitOffset]
    66  		remaining             = length
    67  	)
    68  
    69  	if mask != 0x01 {
    70  		curbyte = cur[0] & bitutil.PrecedingBitmask[startBitOffset]
    71  		for mask != 0 && remaining > 0 {
    72  			if g() {
    73  				curbyte |= mask
    74  			}
    75  			mask <<= 1
    76  			remaining--
    77  		}
    78  		cur[0] = curbyte
    79  		cur = cur[1:]
    80  	}
    81  
    82  	var outResults [8]byte
    83  	for remainingBytes := remaining / 8; remainingBytes > 0; remainingBytes-- {
    84  		for i := 0; i < 8; i++ {
    85  			if g() {
    86  				outResults[i] = 1
    87  			} else {
    88  				outResults[i] = 0
    89  			}
    90  		}
    91  		cur[0] = (outResults[0] | outResults[1]<<1 | outResults[2]<<2 |
    92  			outResults[3]<<3 | outResults[4]<<4 | outResults[5]<<5 |
    93  			outResults[6]<<6 | outResults[7]<<7)
    94  		cur = cur[1:]
    95  	}
    96  
    97  	remainingBits := remaining % 8
    98  	if remainingBits > 0 {
    99  		curbyte = 0
   100  		mask = 0x01
   101  		for ; remainingBits > 0; remainingBits-- {
   102  			if g() {
   103  				curbyte |= mask
   104  			}
   105  			mask <<= 1
   106  		}
   107  		cur[0] = curbyte
   108  	}
   109  }
   110
View as plain text