BitModule

[idle]

Collection of structures for working with bits

BitVector:
Creates an output stream of arbitrary bit patterns, should handle up to 32 bits wide
Vector grows automatically appending bit patterns to the stream

BitArray:
An array of bits
useful for membership tests

Bloom Filter:
Probabilistic data structure for unbounded membership tests
useful for cache checks and membership tests

BitTrie
Array based bittrie for key pair look ups
similar use as a map but with numeric keys
Generally a little faster than a map

Features
All data structures can be saved to disk and loaded from file or memory
Bitarray BitVector and Bloom filter include logical set operations not, or, xor, and

If you have any more ideas please suggest!
v 1.3.8
Updated to pb 5.42 lts
exported hash functions
removed crc32
added asm popcount x86/x64 and SSE 4.2 for bitcount
added shift left right (nicked from wilbert)

v1.3.7
fixed bitarray bit order
v1.3.6
added GetBitCount; fixed reallocation bug in bittrie
v1.3.5
added ;NOT, OR, XOR, AND for bitarray bitvector bloomfilter classes
v1.3.4
fixed bloom added more hashes
v1.3.3
improved trie performance
v1.3.2
Added Catch to load from memory
v1.3.1
fixed Trie walk
v1.3
Added persistent storage Save and Load functions
Redid Trie

v1.2
Added Bit Trie
Trie Walk function needs a bit a tweak

v1.1
Changed BitVector Get to GetBuffer
Added BitVector Get(index,BitCount)

Code: Select all

EnableExplicit

DeclareModule BitModule
;BitModule
;Author Idle 17/11/13
;PB 5.42+
;Description
 
;BitVector  ; Sets n number of bits with a given value into a memory stream which automatically grows:
                     ; useful if working with arbitary bitsizes to produce an indexable array or output stream 
                     
;BitArray     ; set, get or toggle a bit at an index in the array
                     ;useful for membership tests 1 bit per index
                     
;Bloom Filter  ;probablistic structure to determine if an item exists in a set.
                          ;useful for membership tests of unbounded data sets
                          ;note can give false positives if a key doesn't exist in the set
                         
;BitTrie     ;store and retrieve integer key pair values   
                   ;useful as a replacement to a map   
                   
;Features
;All data structures can be saved to disk and loaded from file or memory
;bitarray bitvector and bloomfilter include logical operations not, or, xor, and

;v1.3.8 
;   shiftleft shiftright for bitarray bitvector
;v1.3.7
;  fixed bitarray bit order   
;v1.3.6
;  added get bit count; fixed bug in bittrie reallocation;
;v1.3.5
 ;NOT, OR, XOR, AND for bitarray bitvector bloomfilter classes
;v1.3.4
;tuned up bloom added more hash functions
;v1.3.3
;improved trie time
;v1.3.2
;Added catch
;v1.3.1
;fixed trie walk
;v1.3
;Added Save and load
;modified Trie to work from file
;V1.2
;Added BitTrie
;v1.1
;changed bitvector get to getbuffer
;added     bitvector get(index,bitcount) 
   
Enumeration 1 
   #OP_OR
   #OP_AND
   #OP_XOR
EndEnumeration 

Interface IBitVector
   Set(val,bitcount)          ;adds a value to the bitvector stream eg: val=%0101010, bitcount=7   
   Get(index,bitcount)    ;Get bits from the index by number of bits eg index =7, bitcount =3 
   GetBuffer()                    ; Returns pointer to the buffer
   SetBuffer(*mem,len)  ;Set the buffer to use
   BinOP(bitvector,OP)    ;Perform a binary operation on another bit vector OR XOR AND bitModule::#OP_OR
   Not()                                   ;nots the buffer
   ShiftLeft()                      ;shift left number of bits  
   ShiftRight()                     ;shift right number of bits
   Save(file.s,CompressLevel=9)   ;save a compressed bit buffer to file
   Load(file.s)                                    ;load a compressed bit buffer from file
   Catch(*mem,len)                        ;catch a saved bit buffer from a datasection
   BitSize()                    ;size of stream in bits 
   ByteSize()                 ;size in stream in bytes
   BitCount()                 ;popcount number of bits set 
   Clear()
   Free() 
EndInterface   

Interface IBitArray
   Set(index)                          ;Set bit at position  to 1
   ReSet(index)                     ;Reset bit at position to 0
   Toggle(index)                    ;Toggle value of bit at position 
   Get(index)                         ;Check if the bit is set returns > 0 if true
   GetBuffer()                    ; Returns pointer to the buffer
   BinOP(bitarray,OP)             ;Perform a binary operation on another bit array OR XOR AND bitModule::#OP_OR
   BiNOPNew(bitarray,OP)          ;Perform a binary operation on another bit array and returns a new bitarray  
   Not()                                    ;Nots the buffer 
   ShiftLeft()                      ;shift left number of bits  
   ShiftRight()                     ;shift right number of bits
   Save(file.s,CompressLevel=9)   ;save compressed bitarray to file
   Load(file.s)                                     ;load compressed bitarray from file 
   Catch(*mem,len)                         ;catch compressed bitarray from datasection
   BitSize()                     ;size of array in bits
   ByteSize()                  ;size in array in bytes
   BitCount()
   Clear()
   Free()                             
EndInterface 

Interface IBloomFilter
   Set(*key,len)                              ;Set the key  ;*key, pointer to the memory string or integer, 
   Get(*key,len)                             ;look up a key in the filter   
   GetBuffer()                                ; Returns pointer to the buffer
   BinOP(bloomfilter,OP)          ;Perform a binary operation on another bloom filter OR XOR AND bitModule::#OP_OR   
   Not()                                             ;Nots the buffer 
   Save(file.s,CompressLevel=9)   ;save compresed bloom to file
   Load(file.s)                                     ;load compressed bloom from file
   Catch(*mem,len)                         ;catch compressed bloom from datasection
   BitSize()
   ByteSize()
   BitCount()
   Clear()
   Free()
EndInterface   

Prototype BitTrieCB(value.i,*userdata=0,*userdata1=0)

Interface IBitTrie      ;bit Trie
   Set(key.i,value=1)      ;store a value with the key 
   Get(key.i)                     ;get the value with the key 
   GetBuffer()               ;get the pointer to the buffer
   Walk(*cb.bitTrieCB,*usrdata=0,*usrdata1=0)   ;dumps the trie unordered
   Save(file.s,CompressLevel=9)  ;save the trie to file
   Load(file.s)                                   ;load the trie from file
   Catch(*mem,len)                       ;catch the trie from a data section
   ByteCount()                               ;size of trie
   NumItems()
   Clear()
   Free()
EndInterface   

Declare.q Hash_Rs(*mem,len.i) 
Declare.q Hash_Sax(*mem,len.i)
Declare.q Hash_Sdbm(*mem,len.i) 
Declare.q Hash_Js(*mem,len.i)
Declare.q Hash_Fnv32_1(*mem,len.i)
Declare.q Hash_Fnv32_1a(*mem,len.i) 
Declare.q Hash_Adler32(*mem,len.i)  

Declare  New_BitVector(size=64,*data=0)
Declare  New_BitArray(size=64,*data=0) 
Declare  New_BitTrie(size=64)
Declare  New_BloomFilter(Items,NumberOfKeys=4,MaxErrorRate.f=0.999) 

EndDeclareModule

Module BitModule
 
CompilerIf #PB_Compiler_OS = #PB_OS_Windows
   
 ImportC "zlib.lib"
    compress2(*dest,*destlen,*source,sourcelen,level)
    uncompress(*dest,*destlen,*source,sourcelen)
 EndImport
CompilerElse
  ImportC "-lz"   
    compress2(*dest,*destlen,*source,sourcelen,level)
    uncompress(*dest,*destlen,*source,sourcelen)
  EndImport
CompilerEndIf

Enumeration 1
   #obj_bitarray
   #obj_bitvector
   #obj_bloom
   #obj_bittire
EndEnumeration

Structure BitBufInfo
   Size.q
   Bytesused.q
   Position.q
   Misc.l
   type.l
 EndStructure 
 
 Structure BitBuffer
   *vt
   inf.bitbufinfo
   *buf
 EndStructure   

Structure node   
    inext.l[2]   
    value.i                 
EndStructure         

Structure BitTrie Extends bitBuffer
  avail.i
  count.i
EndStructure

Procedure New_BitTrie(size=64)
   Protected *this.BitTrie
   *this = AllocateMemory(SizeOf(bittrie))
   *this\vt = ?vt_BitTrie
   *this\inf\size = Size*SizeOf(node)
   *this\inf\Bytesused = *this\inf\size
   *this\inf\Position=SizeOf(node)
   *this\inf\type = #obj_bittire
   *this\buf = AllocateMemory(*this\inf\Size)
   *this\avail = *this\inf\size-SizeOf(node)
    ProcedureReturn *this
EndProcedure   

Procedure BitTrie_Add(*this.bittrie,key.i,val.i=1)
   Protected *node.node,idx,a,lp,offset
   
   CompilerIf SizeOf(Integer) = 8
     !bsr qword rax , qword [p.v_key]   
     !mov [p.v_lp] , rax 
   CompilerElse
      !bsr dword eax , dword [p.v_key]   
      !mov [p.v_lp] , eax   
   CompilerEndIf   
   
   *node = *this\buf
   
   If key <> 0
      For a = lp To 0 Step -1
         idx = (key >> a) & 1
         If *node\inext[idx]     
            offset = *node\inext[idx]
            *node = *this\buf + offset
         ElseIf *this\avail  > 0
            offset = *this\inf\Position
            *node\inext[idx] =  offset
            *node = *this\buf  + offset
            *this\avail - SizeOf(node)
            *this\inf\Position+SizeOf(node)
            *this\inf\Bytesused = *this\inf\Position 
         Else
            *this\avail = 64*SizeOf(node)
            *this\inf\size + *this\avail
            *this\buf = ReAllocateMemory(*this\buf,*this\inf\size)
            *node = *this\buf + offset
            offset = *this\inf\Position
            *node\inext[idx] = offset ;
            *node = *this\buf  + offset
            *this\avail - SizeOf(node)
            *this\inf\Position+SizeOf(node)
            *this\inf\Bytesused = *this\inf\Position
         EndIf
      Next   
   EndIf
   If *node
     *node\value = val
     *this\count + 1 
   EndIf   
EndProcedure

Procedure BitTrie_Get(*this.bittrie,key.i)
   Protected *node.node,value,a,idx,lp
   
   CompilerIf SizeOf(Integer) = 8
     !bsr qword rax , qword [p.v_key]   
     !mov [p.v_lp] , rax 
   CompilerElse
      !bsr dword eax , dword [p.v_key]   
      !mov [p.v_lp] , eax   
   CompilerEndIf   
   
   *node = *this\buf
   
   If key <> 0
      For a = lp To 0 Step -1
         idx = (key>>a) & 1
         If *node   
            If *node\inext[idx]     
               *node = *this\buf + *node\inext[idx]
            Else
               ProcedureReturn 0
            EndIf
         Else
            ProcedureReturn 0 
         EndIf
      Next   
   EndIf
   If *node
      ProcedureReturn *node\value
   EndIf 
EndProcedure   
 
Procedure BitTrie_Walk(*this.bitTrie,*cb.bitTrieCB,*userdata=0,*userdata1=0)
   Protected *node.node,pos
   If *cb
      While pos < *this\inf\Bytesused
          *node = *this\buf +pos
          If *node\value 
            *cb(*node\value,*userdata,*userdata1)
          EndIf   
          pos + SizeOf(node)     
      Wend     
  EndIf
EndProcedure

Procedure BitTrie_NumItems(*this.bitTrie)
  ProcedureReturn *this\count 
EndProcedure   
 
Procedure.q Hash_Rs(*mem,len) ;Rs
   Protected hash.l, *pta.Ascii,a.l,b.l
   a = 378551
   b = 63689
   *pta =*mem
   For c = 1 To len   
     hash * a
     hash + *pta\a
     a * b
     *pta+1
   Next
   ProcedureReturn hash  & $FFFFFFFF
EndProcedure

Procedure.q Hash_Sax(*mem,len) ;sax
   Protected hash.l, *pta.Ascii
   *pta =*mem
   For a = 1 To len   
      hash ! (((hash <<5) + (hash >> 2)) + *pta\a)
      *pta+1
   Next
   ProcedureReturn hash & $FFFFFFFF
EndProcedure   

Procedure.q Hash_Sdbm(*mem,len) ;sdbm
   Protected hash.l, *pta.Ascii
   *pta =*mem
   For a = 1 To len   
      hash = *pta\a + ((hash<<6) + (hash<<16) - hash)       
      *pta+1   
   Next
   ProcedureReturn hash  &  $FFFFFFFF
EndProcedure

Procedure.q Hash_Js(*mem,len)  ;js
   Protected hash.l, *pta.Ascii
   hash = 1315423911;
   *pta =*mem
   For a = 1 To len   
      hash ! ((hash<<5)+*pta\a) +(hash>>2)
      *pta+1
   Next
   ProcedureReturn hash  &  $FFFFFFFF
EndProcedure 

Procedure.q Hash_Fnv32_1(*mem,len) ;Fnv32-1
   Protected p.l,hash.l, *pta.Ascii
   p = 16777619
   hash = 2166136261
   *pta =*mem
   For a = 1 To len   
      hash * p
      hash ! *pta\a
     *pta+1
   Next
   ProcedureReturn hash  & $FFFFFFFF
EndProcedure

Procedure.q Hash_Fnv32_1a(*mem,len) ;fnv32-1a
   Protected p.l,hash.l, *pta.Ascii
   p = 16777619
   hash = 2166136261
   *pta =*mem
   For a = 1 To len   
      hash ! *pta\a
      hash * p
      *pta+1
   Next
   ProcedureReturn hash  & $FFFFFFFF
EndProcedure

Procedure.q Hash_Adler32(*mem,len)  ;adler32 
   Protected pa.l,pb.l,hash.l, *pta.Ascii
   *pta =*mem
     For a = 1 To len   
        pa + *pta\a
        pa % 65521
        pb + a
        pb % 65521
        *pta+1
     Next     
     hash = ((pb << 16) | pa)
    ProcedureReturn hash  & $FFFFFFFF
     
EndProcedure
 
Prototype.q hash(*mem,len)

Structure bloom Extends bitbuffer
     *hashFn.hash[7]
EndStructure  

Procedure New_BloomFilter(Items,NumberOfKeys=4,MaxErrorRate.f=0.999)
   Protected *this.bloom 
   *this = AllocateMemory(SizeOf(bloom))
   
   If NumberOfKeys > 6 
     NumberOfKeys = 6 
   EndIf   
        
   If *this
      *this\vt = ?vt_bloom
      *this\inf\Position = (-(NumberOfKeys * (items))) / (Log(1 - Pow((MaxErrorRate),1/NumberOfKeys )))
      *this\inf\Size = *this\inf\Position >> 3   
      *this\inf\BytesUsed = *this\inf\size
      *this\inf\misc =NumberOfKeys
      *this\inf\type = #obj_bloom
      *this\buf = AllocateMemory(*this\inf\size)
      *this\hashFn[0] = @Hash_Rs()
      *this\hashFn[1] = @Hash_Sax()
      *this\hashFn[2] = @Hash_Sdbm()
      *this\hashFn[3] = @Hash_Js()
      *this\hashFn[4] = @Hash_Fnv32_1()
      *this\hashFn[5] = @Hash_Fnv32_1a()
      *this\hashFn[6] = @Hash_Adler32()
            
      ProcedureReturn *this
   EndIf 
EndProcedure

Procedure  Bloom_Set(*this.Bloom,*key,len)
   Protected hash.q,a.i,*ta.Ascii
   
   For a = 0 To *this\inf\Misc-1
      hash =  *this\hashFn[a](*key,len)
      hash % *this\inf\Position 
      *ta = *this\buf+(hash>>3)
      *ta\a | (1 << (hash & $07))
    Next     
   
EndProcedure

Procedure Bloom_Get(*this.Bloom,*Key,len)
   Protected hash.q,tret,retrn,a,*ta.Ascii
   For a = 0 To *this\inf\Misc-1
      hash =  *this\hashFn[a](*key,len)
      hash % *this\inf\Position
      *ta = *this\buf+(hash>>3)
      tret = (*ta\a & (1 << (hash & $07))) 
      If tret = 0
         ProcedureReturn 0
      Else     
         retrn + 1
      EndIf     
   Next   
   
   If retrn = *this\inf\Misc ;number of keys
      ProcedureReturn #True
   Else
      ProcedureReturn #False
   EndIf
   
EndProcedure

Procedure New_BitArray(sizebytes=64,*data=0)
   Protected *bv.bitbuffer
   *bv = AllocateMemory(SizeOf(bitbuffer))
   If *bv
      *bv\vt = ?vt_bitArray
      *bv\buf = AllocateMemory(sizebytes)
      If *bv\buf 
         *bv\inf\Size = sizebytes
         *bv\inf\BytesUsed = sizebytes
         *bv\inf\Position = 0
         *bv\inf\type = #obj_bitarray
         If *data 
           CopyMemory(*data,*bv\buf,sizebytes) 
           *bv\inf\Position = sizebytes * 8 
         EndIf  
         ProcedureReturn *bv
      EndIf
   EndIf
EndProcedure

Procedure BitArray_Set(*this.bitbuffer,index)
   Protected *ta.Ascii, *bv.bitbuffer,tsize 
   Protected bit.a 
   If ((index) >> 3) >= *this\inf\size
      *this\inf\size = index + 64
      *this\inf\BytesUsed = *this\inf\size
      *this\buf = ReAllocateMemory(*this\buf,*this\inf\Size)
   EndIf
   If *this\buf
      *ta = *this\buf + ((index)>>3)
      *ta\a | (1 << (7-(index & $07)))
   EndIf
EndProcedure   

Procedure BitArray_ReSet(*this.bitbuffer,index)
   Protected *ta.Ascii 
    If ((index) >> 3) >= *this\inf\size
      *this\inf\size = index + 64
      *this\inf\BytesUsed = *this\inf\size
      *this\buf = ReAllocateMemory(*this\buf,*this\inf\size)
   EndIf
   If *this\buf
      *ta = *this\buf + ((index)>>3)
      If  *ta\a & (1 << (7-(index & $07)))
        *ta\a ! (1 << (7-(index & $07)))
      EndIf
     
   EndIf
EndProcedure 

Procedure BitArray_Toggle(*this.bitbuffer,index)
   Protected *ta.Ascii 
    If ((index) >> 3) >= *this\inf\size
      *this\inf\size = index + 64
      *this\inf\BytesUsed = *this\inf\size
      *this\buf = ReAllocateMemory(*this\buf,*this\inf\size)
   EndIf
   If *this\buf
      *ta = *this\buf + ((index)>>3)
      *ta\a ! (1 << (7-(index & $07)))
   EndIf
EndProcedure   

Procedure BitArray_Get(*this.bitbuffer,index)
   Protected *ta.Ascii,idx
   If ((index) >> 3) <= *this\inf\size
      *ta = *this\buf+(index>>3)
      If  (*ta\a & (1 << (7-(index & $07))))
          ProcedureReturn 1
      EndIf   
   EndIf           
EndProcedure

Procedure New_BitVector(sizebytes=64,*data=0)
   Protected *bv.bitBuffer
   *bv = AllocateMemory(SizeOf(bitbuffer))
   If *bv
      *bv\vt = ?vt_bitvector
      *bv\buf = AllocateMemory(sizebytes)
      If *bv\buf 
         *bv\inf\size = sizebytes
         *bv\inf\BytesUsed = 0
         *bv\inf\Position = 0
         *bv\inf\type = #obj_bitvector
         If *data 
           CopyMemory(*data,*bv\buf,sizebytes) 
           *bv\inf\Position = sizebytes * 8 
           *bv\inf\Bytesused = sizebytes
         EndIf  
         ProcedureReturn *bv
      EndIf
   EndIf
EndProcedure

Procedure BitVector_Set(*this.bitbuffer,val,bitcount)
   Protected *ti.quad,tsize
   tsize = (*this\inf\Position+bitcount) >> 3
   If tsize >= *this\inf\size
      *this\inf\size = tsize +64
      *this\buf = ReAllocateMemory(*this\buf,*this\inf\size)
   EndIf
   If *this\buf
      *ti = *this\buf + ((*this\inf\Position)>>3)
      *ti\q | (val << ( *this\inf\Position & $07))
      *this\inf\Position + bitcount
      *this\inf\BytesUsed =  Round(*this\inf\Position / 8,#PB_Round_Up) ;*this\inf\Position >> 3
   EndIf
EndProcedure   

Procedure BitVector_Get(*this.bitbuffer,index,bitcount)
   Protected mask.q,*ti.quad,shift
   mask = $FFFFFFFF
   mask >> (32-bitcount)
   If *this\buf
      *ti = *this\buf + ((index)>>3)
      shift = (index & $07)
      ProcedureReturn  (*ti\q & (mask << shift)) >> shift   
   EndIf
   
EndProcedure   

Procedure BitBuffer_GetBuffer(*this.bitbuffer)
   If *this
      ProcedureReturn *this\buf
   EndIf           
EndProcedure   

Procedure BitBuffer_SetBuffer(*this.bitbuffer,*mem,len)
   If *this
      *this\buf = *mem
      *this\inf\Bytesused = len
      *this\inf\Size = len
   EndIf           
EndProcedure   

Procedure BitBuffer_BiNOP(*this.bitbuffer,*that.bitbuffer,OP)
   Protected *pa.Ascii,*pb.Ascii,a
   
   If *this\inf\Size <= *that\inf\Size
      *this\buf = ReAllocateMemory(*this\buf,*that\inf\Size)
      *this\inf\Size = *that\inf\Size
      *this\inf\Position = *that\inf\Position
      *this\inf\Bytesused = *that\inf\Bytesused
      *this\inf\Misc = *that\inf\Misc
   EndIf   
   
   *pa = *this\buf
   *pb = *that\buf
   
   For a = 0 To *that\inf\Size-1
      Select OP
      Case #OP_OR
         *pa\a | *pb\a
      Case #OP_AND
         *pa\a & *pb\a
      Case #OP_XOR
          *pa\a ! *pb\a
      EndSelect   
      *pa+1
      *pb+1
    Next
   
EndProcedure

Procedure BitBuffer_BiNOPNew(*this.bitbuffer,*that.bitbuffer,OP)
   Protected *pa.Ascii,*pb.Ascii,*pc.Ascii,a
   Protected *result.BitBuffer = New_BitArray(*this\inf\Size)
     
   *pa = *this\buf
   *pb = *that\buf
   *pc = *result\buf 
   
   For a = 0 To *that\inf\Size;-1
      Select OP
      Case #OP_OR
       *pc\a =  *pa\a | *pb\a
      Case #OP_AND
       *pc\a = *pa\a & *pb\a
      Case #OP_XOR
       *pc\a = *pa\a ! *pb\a
      EndSelect   
      *pa+1
      *pb+1
      *pc+1
    Next
    ProcedureReturn *result 
EndProcedure


Procedure BitBuffer_Not(*this.bitbuffer)
   Protected *pa.Ascii,a 
   *pa = *this\buf
   
   For a = 0 To *this\inf\Size
      *pa\a  = ~*pa\a
       *pa+1
   Next
   
 EndProcedure
 
 Procedure BitBuffer_ShiftLeft(*this.bitbuffer)
   Protected *data,length.l 
  *data = *this\buf 
  length = *this\inf\Size
  !xor eax, eax
  !mov ecx, [p.v_length]
  !dec ecx
  !jc slb_exit
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    !mov rdx, [p.p_data]
    !slb_loop:  
    !mov ah, [rdx + rcx]
    !shl eax, 1
    !mov [rdx + rcx], ah
  CompilerElse
    !mov edx, [p.p_data]
    !slb_loop:  
    !mov ah, [edx + ecx]
    !shl eax, 1
    !mov [edx + ecx], ah
  CompilerEndIf
  !shr eax, 9
  !sub ecx, 1
  !jnc slb_loop
  !slb_exit:
  !shr eax, 7
  ProcedureReturn
EndProcedure

Procedure BitBuffer_ShiftRight(*this.bitbuffer)
  Protected *data,length.l 
  *data = *this\buf 
  length = *this\inf\Position
  !xor eax, eax
  !mov ecx, [p.v_length]
  !and ecx, ecx
  !jz srb_exit
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    !mov rdx, [p.p_data]
    !srb_loop:  
    !mov ah, [rdx]
    !shr eax, 1
    !mov [rdx], ah
    !inc rdx
  CompilerElse
    !mov edx, [p.p_data]
    !srb_loop:  
    !mov ah, [edx]
    !shr eax, 1
    !mov [edx], ah
    !inc edx
  CompilerEndIf  
  !shl eax, 9
  !dec ecx
  !jnz srb_loop
  !srb_exit:
  !shr eax, 16
  !and eax, 1
  ProcedureReturn
EndProcedure

CompilerIf SizeOf(Integer) = 4

Procedure _popcountmem(*mem.long,len.l) 
  Protected result,a,b 
       
  !mov eax, [p.v_len] 
  !and eax, 3 
  !mov edx, [p.v_len] 
  !sub edx,eax 
  !mov [p.v_a],edx
  !mov [p.v_b],eax 
  !xor ecx,ecx
  !lwhile:
  !cmp ecx, [p.v_a] 
  !jge lend
  !mov eax, [p.p_mem] 
  !mov eax, [eax + ecx]
  !mov edx, eax
  !shr edx, 1
  !and edx, 0x55555555 
  !sub eax,edx 
  !mov edx, eax       
  !and eax, 0x33333333 
  !shr edx, 2 
  !and edx, 0x33333333
  !add eax,edx
  !mov edx, eax 
  !shr edx, 4 
  !add eax,edx 
  !and eax, 0x0f0f0f0f
  !imul eax, 0x01010101
  !shr eax, 24
  !add [p.v_result],eax   
  !add ecx,4
  !jmp lwhile
  !lend:
  
  !mov eax, [p.p_mem] 
  !mov eax, [eax + ecx]
    
  !mov edx, [p.v_b]
  !jmp dword [JT_remain + edx * 4]
  !JT_remain dd le,l1,l2,l3,l4
    
  !l1: 
  !and eax, 0xff
  !jmp le
  !l2:
  !and eax, 0xffff
  !jmp le 
  !l3:
  !and eax, 0xffffff
  !jmp le 
  !l4:
  !le: 
   
  !mov edx, eax
  !shr edx, 1
  !and edx, 0x55555555 
  !sub eax,edx 
  !mov edx, eax       
  !and eax, 0x33333333 
  !shr edx, 2 
  !and edx, 0x33333333
  !add eax,edx
  !mov edx, eax 
  !shr edx, 4 
  !add eax,edx 
  !and eax, 0x0f0f0f0f
  !imul eax, 0x01010101
  !shr eax, 24
  !add [p.v_result],eax   
   
  ProcedureReturn result   
EndProcedure   

Procedure _popcountmemSSE(*mem,len) 
  Protected result,a,b 
       
  !mov eax, [p.v_len] 
  !and eax, 3 
  !mov edx, [p.v_len] 
  !sub edx,eax 
  !mov [p.v_a],edx
  !mov [p.v_b],eax 
  !xor ecx,ecx
  !lwhile1:
  !cmp ecx, [p.v_a] 
  !jge lend1
  
  !mov eax, [p.p_mem] 
  !mov eax, [eax + ecx]
  !popcnt eax,eax   
  !add [p.v_result],eax   
  !add ecx,4
   
  !jmp lwhile1
  !lend1:
  
  !mov eax, [p.p_mem] 
  !mov eax, [eax + ecx]
    
  !mov edx, [p.v_b]
  !jmp dword [JT_remain1 + edx * 4]
  !JT_remain1 dd lle,ll1,ll2,ll3,ll4
    
  !ll1: 
  !and eax, 0xff
  !jmp lle
  !ll2:
  !and eax, 0xffff
  !jmp lle 
  !ll3:
  !and eax, 0xffffff
  !jmp lle 
  !ll4:
  !lle: 
  
  !mov edx,eax
  !popcnt eax,edx   
  !add [p.v_result],eax   
  
  ProcedureReturn result  
EndProcedure   


CompilerElse 

Procedure _popcountmem(*mem,len) 
  Protected result,a,b 
       
  !mov rax, [p.v_len] 
  !And rax, 3 
  !mov rdx, [p.v_len] 
  !sub rdx,rax 
  !mov [p.v_a],rdx
  !mov [p.v_b],rax 
  !xor rcx,rcx
  !lwhile:
  !cmp rcx, [p.v_a] 
  !jge lend
  !mov rax, [p.p_mem] 
  !mov eax, [rax + rcx]
  !mov edx, eax
  !shr edx, 1
  !and edx, 0x55555555 
  !sub eax,edx 
  !mov edx, eax       
  !and eax, 0x33333333 
  !shr edx, 2 
  !and edx, 0x33333333
  !add eax,edx
  !mov edx, eax 
  !shr edx, 4 
  !add eax,edx 
  !and eax, 0x0f0f0f0f
  !imul eax, 0x01010101
  !shr eax, 24
  !add [p.v_result],eax   
  !add rcx,4
  !jmp lwhile
  !lend:
  
  !mov rax, [p.p_mem] 
  !mov eax, [rax + rcx]
  
  !lea rdx, [JT_remain]
  !mov rcx, [p.v_b]
  !jmp qword [rdx + rcx * 8]
  !JT_remain dq le,l1,l2,l3,l4
    
  !l1: 
  !and eax, 0xff
  !jmp le
  !l2:
  !and eax, 0xffff
  !jmp le 
  !l3:
  !and eax, 0xffffff
  !jmp le 
  !l4:
  !le: 
   
  !mov edx, eax
  !shr edx, 1
  !and edx, 0x55555555 
  !sub eax,edx 
  !mov edx, eax       
  !and eax, 0x33333333 
  !shr edx, 2 
  !and edx, 0x33333333
  !add eax,edx
  !mov edx, eax 
  !shr edx, 4 
  !add eax,edx 
  !and eax, 0x0f0f0f0f
  !imul eax, 0x01010101
  !shr eax, 24
  !add [p.v_result],eax   
   
  ProcedureReturn result   
EndProcedure   

Procedure _popcountmemSSE(*mem,len) 
  Protected result,a,b 
       
  !mov rax, [p.v_len] 
  !and rax, 7 
  !mov rdx, [p.v_len] 
  !sub rdx,rax 
  !mov [p.v_a],rdx
  !mov [p.v_b],rax 
  !xor rcx,rcx
  !lwhile1:
  !cmp rcx, [p.v_a] 
  !jge lend1
  
  !mov rax, [p.p_mem] 
  !mov rax, [rax + rcx]
  !popcnt rax,rax   
  !add [p.v_result],rax   
  !add rcx,8
   
  !jmp lwhile1
  !lend1:
  
  !mov rax, [p.p_mem] 
  !mov rax, [rax + rcx]
    
  !lea rdx, [JT_remain1]
  !mov rcx, [p.v_b]
  !jmp qword [rdx + rcx * 8]
  !JT_remain1 dq lle,ll1,ll2,ll3,ll4,ll5,ll6,ll7,ll8
    
  !ll1: 
  !and rax, 0xff
  !jmp lle
  !ll2:
  !and rax, 0xffff
  !jmp lle 
  !ll3:
  !and rax, 0xffffff
  !jmp lle 
  !ll4:
  !mov rdx,0xffffffff
  !and rax, rdx
  !jmp lle 
  !ll5:
  !mov rdx, 0xffffffffff
  !and rax, rdx
  !jmp lle 
  !ll6:
  !mov rdx,0xffffffffffff
  !and rax, rdx
  !jmp lle
  !ll7:
  !mov rdx,0xffffffffffffff 
  !and rax, rdx
  !jmp lle
  !ll8:
  !lle: 
  
  !mov rdx,rax
  !popcnt rax,rdx   
  !add [p.v_result],rax   
  
  ProcedureReturn result  
EndProcedure   
  
CompilerEndIf 
 
Prototype PopCountMem(*mem,len) 
Global PopCountMem.PopCountMem 

Procedure InitpopCount() 
  Protected result 
  !mov eax, 1
  !cpuid
  !shr ecx, 23
  !and ecx, 1
  !mov [p.v_result],ecx 
  If result 
    popcountmem = @_popcountmemSSE() 
  Else 
    popcountmem = @_popcountmem()
 EndIf    
EndProcedure 

Procedure BitBuffer_GetBitCount(*this.bitbuffer) ;popcount
   If *this
     If Not popcountmem
       InitpopCount() 
     EndIf   
     ProcedureReturn PopCountMem(*this\buf,*this\inf\Size) 
   EndIf   
EndProcedure 

Procedure BitBuffer_GetBitSize(*this.bitbuffer)
   If *this
       ProcedureReturn *this\inf\BytesUsed * 8 
   EndIf
EndProcedure       

Procedure BitBuffer_GetByteSize(*this.bitbuffer)
  If *this
      ProcedureReturn *this\inf\BytesUsed
  EndIf
EndProcedure

Procedure BitBuffer_SaveToFile(*this.bitbuffer,file.s,CompressLevel=9)
   Protected fn,len,*src,*dst,destlen,srclen 
   fn = OpenFile(#PB_Any,file)
   If fn
      srclen = *this\inf\BytesUsed+SizeOf(BitBufInfo)
      *src = AllocateMemory(srclen)
      destlen = srclen * 1.5
      *dst = AllocateMemory(destlen)
      If  *src And *dst      ;bit stupid here need to rework structures so don't have to copy before compress                                                 
         CopyMemory(@*this\inf,*src,SizeOf(BitBufInfo))
         CopyMemory(*this\buf,*src+SizeOf(BitBufInfo),*this\inf\BytesUsed)
         If  compress2(*dst,@destlen,*src,srclen ,CompressLevel) = 0   
            len = WriteLong(fn,srclen)
            len + WriteData(fn,*dst,destlen)
            CloseFile(fn)
            FreeMemory(*src)
            FreeMemory(*dst)
            ProcedureReturn len     
         EndIf 
      EndIf 
   EndIf   
EndProcedure   

Procedure BitBuffer_LoadFile(*this.bitbuffer,file.s)
   Protected fn,destlen,srclen,*src,*dst
  fn = OpenFile(#PB_Any,file)
   If fn
      destlen = ReadLong(fn)
      *dst = AllocateMemory(destlen)
       srclen = Lof(fn)-4
       *src = AllocateMemory(srclen)
        ReadData(fn,*src,srclen)
        If uncompress(*dst,@destlen,*src,srclen) = 0
           CopyMemory(*dst,@*this\inf,SizeOf(BitBufInfo))
           FreeMemory(*this\buf)
           *this\buf = AllocateMemory(*this\inf\size)
           CopyMemory(*dst+SizeOf(BitBufInfo),*this\buf,destlen-SizeOf(BitBufInfo))
           FreeMemory(*dst)
           FreeMemory(*src)
           CloseFile(fn) 
           ProcedureReturn 1
      EndIf
   EndIf
 EndProcedure   
 
 Procedure BitBuffer_Catch(*this.bitbuffer,*mem,len)
   Protected destlen,srclen,*src,*dst
   If *mem
      destlen = PeekL(*mem)
      *mem+4
      *dst = AllocateMemory(destlen)
       srclen = len-4
       If uncompress(*dst,@destlen,*mem,srclen) = 0
           CopyMemory(*dst,@*this\inf,SizeOf(BitBufInfo))
           FreeMemory(*this\buf)
           *this\buf = AllocateMemory(*this\inf\size)
           CopyMemory(*dst+SizeOf(BitBufInfo),*this\buf,destlen-SizeOf(BitBufInfo))
           FreeMemory(*dst)
           ProcedureReturn 1
      EndIf
   EndIf
 EndProcedure   
 
 Procedure BitBuffer_Clear(*this.bitbuffer)
   If *this
      FillMemory(*this\buf,*this\inf\Bytesused)
      *this\inf\Position=0
   EndIf
EndProcedure   
 
 
Procedure BitBuffer_Free(*this.bitbuffer)
   If *this
      FreeMemory(*this\buf)
      FreeMemory(*this)
   EndIf
EndProcedure   

DataSection
   vt_Bitvector:
   Data.i @BitVector_Set()
   Data.i @BitVector_Get()
   Data.i @BitBuffer_GetBuffer()
   Data.i @BitBuffer_SetBuffer()
   Data.i @BitBuffer_BinOP()
   Data.i @BitBuffer_Not()
   Data.i @bitBuffer_ShiftLeft()                      
   Data.i @bitbuffer_ShiftRight()                    
   Data.i @BitBuffer_SaveToFile()
   Data.i @BitBuffer_LoadFile()
   Data.i @BitBuffer_Catch()
   Data.i @BitBuffer_GetBitSize()
   Data.i @BitBuffer_GetByteSize()
   Data.i @BitBuffer_GetBitCount()
   Data.i @BitBuffer_Clear()
   Data.i @BitBuffer_Free()
EndDataSection   

DataSection
   vt_BitArray:
   Data.i @BitArray_Set()
   Data.i @BitArray_ReSet()
   Data.i @BitArray_Toggle()
   Data.i @BitArray_Get()
   Data.i @BitBuffer_GetBuffer()
   Data.i @BitBuffer_BinOP()
   Data.i @BitBuffer_BiNOPNew()
   Data.i @BitBuffer_Not()
   Data.i @bitBuffer_ShiftLeft()                      
   Data.i @bitbuffer_ShiftRight()    
   Data.i @BitBuffer_SaveToFile()
   Data.i @BitBuffer_LoadFile()
   Data.i @BitBuffer_Catch()
   Data.i @BitBuffer_GetBitSize()
   Data.i @BitBuffer_GetByteSize()
   Data.i @BitBuffer_GetBitCount()
   Data.i @BitBuffer_Clear()
   Data.i @BitBuffer_Free()
EndDataSection   

DataSection
   vt_bloom:
   Data.i @Bloom_Set()
   Data.i @Bloom_Get()
   Data.i @BitBuffer_GetBuffer()
   Data.i @BitBuffer_BinOP()
   Data.i @BitBuffer_Not()
   Data.i @BitBuffer_SaveToFile()
   Data.i @BitBuffer_LoadFile()
   Data.i @BitBuffer_Catch()
   Data.i @BitBuffer_GetBitSize()
   Data.i @BitBuffer_GetByteSize()
   Data.i @BitBuffer_GetBitCount()
   Data.i @BitBuffer_Clear()
   Data.i @BitBuffer_Free()
EndDataSection   

DataSection
   vt_BitTrie:
   Data.i @BitTrie_Add()
   Data.i @BitTrie_Get()
   Data.i @BitBuffer_GetBuffer()
   Data.i @BitTrie_Walk()
   Data.i @BitBuffer_SaveToFile()
   Data.i @BitBuffer_LoadFile()
   Data.i @BitBuffer_Catch()
   Data.i @BitBuffer_GetByteSize()
   Data.i @BitTrie_NumItems()
   Data.i @BitBuffer_Clear()
   Data.i @BitBuffer_Free()
EndDataSection

EndModule

CompilerIf #PB_Compiler_IsMainFile 

;test code 
OpenConsole()
;Bit Vector class 

Global dir.s, file.s, output.s,a,ct,sz
dir = GetTemporaryDirectory() 

;Set a pattern of bits into a bit Vector automatically grows as needed
Define bv.BitModule::IBitVector  
bv = BitModule::New_BitVector()

bv\Set(%0101,4) 
bv\Set(%0011,4) 
bv\Set(%0111,4) 
bv\Set(%111100001111,12)
bv\Set(%01010,5)
bv\Set(%01101,5)
bv\Set(%11111,5)
bv\Set(%011011,6) 

file = dir + "bitvec.dat"
bv\Save(file) 
bv\Free()
bv = BitModule::New_BitVector()
bv\Load(file)

;print part of the buffer 
PrintN("Peek bit in buffer")
PrintN(RSet(Bin(PeekQ(bv\GetBuffer()),#PB_Quad),bv\BitCount(),"0")) 
PrintN("get bits at indexes")
PrintN(RSet(Bin(bv\Get(0,4)),4,"0")) 
PrintN(RSet(Bin(bv\Get(4,4)),4,"0")) 
PrintN(RSet(Bin(bv\Get(8,4)),4,"0")) 
;print out the byte stream 
Global output.s 
PrintN("dump hex") 
For a = 0 To bv\ByteSize() 
   output + RSet(Hex(PeekA(bv\GetBuffer()+a),#PB_Ascii),2,"0") + " " 
Next    

PrintN(output) 
output="" 

bv\Free()

;bit array class grows as needed  
Define ba.BitModule::IBitArray, baa.BitModule::IBitArray  
ba = BitModule::New_BitArray(4)
baa = BitModule::New_BitArray(4)

For a = 0 To 64 Step 2 
   ba\Set(a)
Next

For a = 1 To 64 Step 2 
   baa\Set(a) 
Next    

file = dir + "bitarray.dat"
ba\Save(file) 
ba\Free()
ba = BitModule::New_BitArray(4)
ba\Load(file) 

For a = 0 To 64 
   output + Str(ba\Get(a))  
Next  
PrintN("Bit Array")
PrintN(output)
output=""

;perfrom some binary opperations on the bitarry 
ba\BinOP(baa, BitModule::#OP_OR)  ;test ba OR baa
For a = 0 To 64 
   output + Str(ba\Get(a))  
Next  
PrintN("Bit Array ba OR baa")
PrintN(output)
ba\BinOP(baa, BitModule::#OP_XOR)  ;test ba XOR baa 
output=""
For a = 0 To 64 
   output + Str(ba\Get(a))  
Next  
PrintN("Bit Array ba XOR baa")
PrintN(output)
PrintN("get bit count")
output="" 
output = "bit count = " + Str(ba\BitCount())
PrintN(output) 


ba\Free() 
baa\Free()

;bloom filter 
Define bc.BitModule::IBloomFilter, size,expect,keys,rate.f    
size = 1<<20  
rate = 0.0001    
keys = 3
expect = rate * size  

bc = BitModule::New_BloomFilter(size,keys,rate);
PrintN("bloom Filter") 

For a = 1 To size  ;fully load the filter 
   bc\set(@a,SizeOf(integer))
Next      

PrintN("Added "+ Str(size)  + " items")

file = dir + "bloom.dat"
bc\Save(file) 
bc\Free()
bc = BitModule::New_BloomFilter(size)
bc\Load(file) 

For a = 1 To size       ;Test if all the items are there, should be no error  
   If Not bc\get(@a,SizeOf(integer))
      PrintN("error should never fail")
   EndIf    
Next   

For a = size To size*2             ;Tests for false positives items that aren't in the filter should be less than (err)
   If bc\get(@a,4) ;
      ct+1
   EndIf    
Next 

PrintN("Checked number of false positives, max expected " +Str(expect) + " actual " + Str(ct))
PrintN("Size bytes " + Str(bc\ByteSize() / 1024 / 1024)  + " mb" ) 


bc\free()

PrintN("BitTrie")  

Procedure TrieCB(value.i) 
   output + Str(value) + " "   
EndProcedure   

;BitTrie  
output = ""
Global bd.BitModule::IBitTrie 
Global be.BitModule::IBitTrie 
Global nsize,st,et,et1 

nsize = 1<<20 
Global NewMap mp(nsize) 

bd = BitModule::New_BitTrie(nsize) ;
PrintN("items " + Str(nsize))

st = ElapsedMilliseconds()
For a = 1 To nsize ;
   bd\Set(a,nsize-a) 
Next 
et = ElapsedMilliseconds()-st 

st = ElapsedMilliseconds()
For a = 1 To nsize ; 
    AddMapElement(mp(),Str(a))  
    mp() = nsize-a 
Next 

et1 = ElapsedMilliseconds()- st  
 
PrintN("trie add " + Str(et) + " map add " + Str(et1))  

st = ElapsedMilliseconds()
For a = 1 To nsize 
   bd\get(a) 
Next 
et = ElapsedMilliseconds() - st 

st = ElapsedMilliseconds() 
For a = 1 To nsize 
   FindMapElement(mp(),Str(a)) 
Next 
et1 = ElapsedMilliseconds()-st 

PrintN("Trie lookup " + Str(et) + " map lookup " + Str(et1))

PrintN("size bytes " + Str(bd\ByteCount()))
output = ""

file = dir + "bittrie.dat"
sz = bd\Save(file) 

bd\Free()
PrintN("Saved Trie  "+ Str(sz) + " bytes") 

be = BitModule::New_BitTrie()
be\Load(file) 
;be\Catch(?BTrieS,?BTrieE-?BTrieS) 
PrintN("loaded Trie")

PrintN("check Trie") 
For a = 1 To 255  
   output + Str(nsize - be\get(a)) + " ";
Next 

PrintN(output)

be\Free() 

Input()

; DataSection 
;    BTrieS:;
;    IncludeBinary "/tmp/bittrie.dat"
;    BTrieE: 
; EndDataSection    

CompilerEndIf 

[davido]

Very nice!

Thank you for sharing.

[netmaestro]

Excellent work and very useful indeed! Thanks for sharing it

[IdeasVacuum]

More than a bit impressive

[idle]

Thanks for the comments
It won't be supper fast being wrapped but hopefully ease of use and utility will out weigh performance concerns

v1.1
Changed BitVector Get to GetBuffer
Added BitVector Get(index,BitCount) to return n bits at index

Ps the bloom filters needs some more work.
needs a few more hashes and the existing ones haven't been verified
if it's to be used it would require that it's tested against the expected data
to make sure it's not producing more false positives than requested

[idle]

v1.2

Added Bit Trie
Trie walk needs a tweek

[davido]

Hi idle,

I got an error running this latest version:

Line 110 : The specified '*MemoryID' is not valid.

*this\buf = ReAllocateMemory(*this\buf,*this\size)

PB 5.21LTS beta 2, 64 bit. Windows 7 64 bit.

[idle]

Thanks, I'll take a look at it on windows seems fine on linux x64
There was an issue in the trie walk procedure also, I've fixed that for the moment but it
needs a bit more thought.

[davido]

Hi idle,

Thanks for all the hard work you must be putting into this.

I forgot to mention that the above occurred in debug mode.
Without debug it crashes within 2 seconds of compiling.

It appears the same on both 32 and 64 bit.

[idle]

Seems to be fine on win32 even with purifier on
pm'd you the current version, can you test it please

[idle]

V1.3

Added Persistent Storage, Save and Load and catch functions
Redid the Trie

[idle]

v1.3.3
improved trie performance a little

[idle]

v1.3.4

Tuned the bloom filter added more hashes

[davido]

Hi idle,

1.3.4 works fine on my system, now.

Unfortunately I didn't get to try 1.3.3

Thank you.

[idle]

v1.3.5

added NOT, OR, XOR, AND for set operations on bitarray, bitvector, bloomfilter classes