bitwise not in byte compare

Question

Say I got a byte like this: 00010001 (with 2 bits ON)

And I wish to compare it to these bytes: {0000 0110, 0000 0011, 0011 0000, 0000 1100 }

The idea is to get the bytes that that don't match; where (byteA & byteX) == 0 For the example I should get/find: {0000 0110, 0000 1100 }

This maybe easy if we write a code where we loop the array of bytes. Here an example:

byte seek = 17;
byte[] pool = {6, 3, 48, 12 };
for(int p=0; p<pool.Length; p++)
{
    if((pool[p] & seek)==0)
    {
        //Usefull
    }
}

Now I wish to do the same without looping the array. Say the array is huge; and I wish to compare each byte with the rest.

for(int p1=0; p1<pool.Length; p1++)
{
    for(int p2=0; p2<pool.Length; p1++)
    {
        if((pool[p1] & pool[p2])==0)
        {
        //byte at p1 works with byte at p2.
        }
    }//for p2
}//for p1

So what are my options? A dictionary won't help me (i think) because if I have my seek byte 0001 0001 I will wan't to find a byte like this: XXX0 XXX0

Any ideas? Thanks a lot for your help;

I welcome C#, C++ or any pseudocode. I am looking for an algorithm; not so much the code

Mike

Answer 1

Here's an entirely different idea, that may or may not work well, depending on what's in your pool.

Put the entire pool into a zero suppressed binary decision diagram. The items from pool would be sets, where the indices for which the bit is 1 are elements of that set. The ZDD is the family of all those sets.
To do a query, form an other ZDD - the family of all sets that do not include the bits which are 1 in seek (that will be a small ZDD, in terms of nodes), then enumerate all sets in the intersection of those ZDD's.

Enumerating all those sets from the intersection is an output sensitive algorithm, but calculating the intersection takes time depending on how big the ZDD's are, so whether it works well depends on whether pool is a nice ZDD (the query zdd is definitely nice). And of course you have to prepare that ZDD, so in any case it'll only help if you plan to query the same pool often.

Answer 2

The great thing about bytes is there are only 256 possibilities.

You could initially create a 2d array 256x256 then just do a look-up into the array with your two values.

You could create the array before hand and then store the result in your main program as a static instance.

static bool[256,256] LookUp = {
 {true, true, true ... },
 ...
 {false, false, false ...}
};

static bool IsUsefule(byte a, byte b) {
 return LookUp[a][b];
}

• edit * Or use Arrays of answer Arrays

The inner array would ONLY contain the bytes that are 'Useful'.

static List<<byte[]> LookUp = new List<byte[]>(256);

static byte[] IsUseful(byte a) {
 return LookUp[a];
}

If 'a' = 0 then IsUseful would return the 255 bytes that have a bit set. This would avoid your inner loop from your example.

Answer 3

One fairly general solution is to "bit-transpose" your data so that you have e.g. a chunk of words containing all the high-order bits of your data, a chunk of words containing all the bits one position down from there, and so on. Then for your two-bit query, you or together two such chunks of words and look for 0 bits - so if a result word is -1 you can skip over it completely. To find where all the 0 bits are in word x, look at popcnt(x ^ (x + 1)): If x = ...10111, then x + 1 = ...11000 so x ^ (x + 1) = 000..01111 - and popcnt will then tell you where the lowest order 0 is. In practice, the big win may be when most of your data does not satisfy the query and you can skip over whole words: when you have a lot of matches the cost of query under any scheme may be small compared to the cost of whatever you plan to do with the matches. In a database, this is http://en.wikipedia.org/wiki/Bitmap_index - lots of info there and pointers to source code.

There are a number of ideas for querying 0/1 data in Knuth Vol 2 section 6.5 - "Binary attributes". Most of these require you to have some idea of the distribution of your data to recognise where they are applicable. One idea from there is generally applicable - if you have any sort of tree structure or index structure, you can keep in the nodes of the tree information on the or/and of everything under it. You can then check your query against that information and you may sometimes find that nothing below that node can possibly match your query, in which case you can skip it all. This is probably most useful if there are connections between the bits, so that e.g. if you divide the pool up just by sorting it and cutting it into chunks, even bits which do not affect the division into chunks are allways set in some chunks and never set in other chunks.

Answer 4

The only thing I can think of is to reduce number of tests:

for(int p1=1; p1<pool.Length; p1++)
{
  for(int p2=0; p2<p1; p1++)
  {
    if((pool[p1] & pool[p2])==0)
    {
      //byte at p1 works with byte at p2.
      //byte at p2 works with byte at p1.
    }
  }
}

Answer 5

First of all, my english is poor but I hope you understand. Also, I know that my answer is a bit late but I think is still useful.

As someone has pointed, best solution is generate a look up table. With this purpose, you have to hardcode every loop iteration case in an array.
Fortunately, we are working with bytes, so it is only possible 256 cases. For instance, if we take your pattern list {3, 6, 12, 48} we get this table:

0: { 3, 6, 12, 48 }
1: { 6, 12, 48 }
2: { 12, 48 }
3: { 12, 48 }
3: { 12, 48 }

    ...

252: { 3 }
253:   -
254:   -
255:   - 

We use the input byte as an index in the look up table to get a list pattern values that doesn't match with the input byte.

Implementation:

I've used Python to generate two headers files. One with a look up table definition, an other one with desired pattern list values. Then, I include this file in a new C project an that's all!

Python Code

#! /usr/bin/env python

from copy import copy
from time import *
import getopt
import sys


class LUPattern:
    __LU_SZ = 256

    BASIC_TYPE_CODE = "const uint8_t"
    BASIC_ID_CODE = "p"
    LU_ID_CODE = "lu"
    LU_HEADER_CODE = "__LUPATTERN_H__"
    LU_SZ_PATTLIST_ID_CODE = "SZ" 
    PAT_HEADER_CODE = "__PATTERNLIST_H__"
    PAT_ID_CODE = "patList"


    def __init__(self, patList):
        self.patList = copy(patList)


    def genLU(self):
        lu = []

        pl = list( set(self.patList) )
        pl.sort()

        for i in xrange(LUPattern.__LU_SZ):
            e = []
            for p in pl:
                if (i & p) == 0:
                    e.append(p)
            lu.append(e)

        return lu


    def begCode(self):
        code = "// " + asctime() + "\n\n" \
            + "#ifndef " + LUPattern.LU_HEADER_CODE + "\n" \
            + "#define " + LUPattern.LU_HEADER_CODE + "\n" \
            + "\n#include <stdint.h>\n\n" \

        return code


    def luCode(self):
        lu = self.genLU()
        pDict = {}

        luSrc = LUPattern.BASIC_TYPE_CODE \
            + " * const " \
            + LUPattern.LU_ID_CODE \
            + "[%i] = { \n\t" % LUPattern.__LU_SZ

        for i in xrange(LUPattern.__LU_SZ):
            if lu[i]:
                pId = "_%i" * len(lu[i])
                pId = pId % tuple(lu[i]) 
                pId = LUPattern.BASIC_ID_CODE + pId

                pBody = "{" + "%3i, " * len(lu[i]) + " 0 }"
                pBody = pBody % tuple(lu[i])

                pDict[pId] = pBody
                luSrc += pId
            else:
                luSrc += "0"

            luSrc += (i & 3) == 3 and (",\n\t") or ", "

        luSrc += "\n};"

        pCode = ""
        for pId in pDict.keys():
            pCode +=  "static " + \
                LUPattern.BASIC_TYPE_CODE + \
                " " + pId + "[] = " + \
                pDict[pId] + ";\n"

        return (pCode, luSrc)        


    def genCode(self):
        (pCode, luSrc) = self.luCode()
        code = self.begCode() \
            + pCode + "\n\n" \
            + luSrc + "\n\n#endif\n\n"

        return code    


    def patCode(self):
        code = "// " + asctime() + "\n\n" \
            + "#ifndef " + LUPattern.PAT_HEADER_CODE + "\n" \
            + "#define " + LUPattern.PAT_HEADER_CODE + "\n" \
            + "\n#include <stdint.h>\n\n"
        code += "enum { " \
            + LUPattern.LU_SZ_PATTLIST_ID_CODE \
            + " = %i, " % len(self.patList) \
            + "};\n\n"
        code += "%s %s[] = { " % ( LUPattern.BASIC_TYPE_CODE, 
                                   LUPattern.PAT_ID_CODE )
        for p in self.patList:
            code += "%i, " % p
        code += "};\n\n#endif\n\n"


        return code



#########################################################


def msg():
    hmsg = "Usage: "
    hmsg += "%s %s %s"  % (
        sys.argv[0], 
        "-p", 
        "\"{pattern0, pattern1, ... , patternN}\"\n\n")
    hmsg += "Options:"

    fmt = "\n%5s, %" + "%is" % ( len("input pattern list") + 3 )
    hmsg += fmt % ("-p", "input pattern list")

    fmt = "\n%5s, %" + "%is" % ( len("output look up header file") + 3 )
    hmsg += fmt % ("-l", "output look up header file")

    fmt = "\n%5s, %" + "%is" % ( len("output pattern list header file") + 3 )
    hmsg += fmt % ("-f", "output pattern list header file")

    fmt = "\n%5s, %" + "%is" % ( len("print this message") + 3 )
    hmsg += fmt % ("-h", "print this message")

    print hmsg

    exit(0)


def getPatternList(patStr):
    pl = (patStr.strip("{}")).split(',')
    return [ int(i) & 255  for i in pl ]


def parseOpt():
    patList = [ 255 ] # Default pattern
    luFile = sys.stdout
    patFile = sys.stdout

    try:
        opts, args = getopt.getopt(sys.argv[1:], "hp:l:f:", ["help", "patterns="])
    except getopt.GetoptError:
        msg()

    for op in opts:
        if op[0] == '-p':
            patList = getPatternList(op[1])
        elif op[0] == '-l':
            luFile = open(op[1], 'w')
        elif op[0] == '-f':
            patFile = open(op[1], 'w')
        elif op[0] == '-h':
            msg()

    return (patList, luFile, patFile)    


def main():
    (patList, luFile, patFile)  = parseOpt()
    lug = LUPattern(patList)
    print >> luFile , lug.genCode()
    print >> patFile, lug.patCode()

    patFile.close()
    luFile.close()


if __name__ == "__main__":
    main()

C Code

Now, after call above script, it'll generate two files: lu.h and pl.h. We must to include that files on our new C project. Here a simple C code example:

#include "pl.h"
#include "lu.h"
#include <stdio.h>


int main(void)
{
  uint32_t stats[SZ + 1] = { 0 };
  uint8_t b;

  while( fscanf(stdin, "%c", &b) != EOF )
  {
    (void)lu[b];
    // lu[b] has bytes that don't match with b
  }

  return 0;
}

Test and benchmark:

I've done some extra stuff to check and get results. There are more code which I've used as a test case unit but I don't paste here (If you wish I'll paste later).

I make two similar versions of a same utility. One use look up table (noloop version) an other one use typical loop (loop version).
loop code are slightly different than noloop code but I try to minimize these differences.

noloop version:

#include "pl.h"
#include "lu.h"
#include <stdio.h>


void doStats(const uint8_t * const, uint32_t * const);
void printStats(const uint32_t * const);


int main(void)
{
  uint32_t stats[SZ + 1] = { 0 };
  uint8_t b;

  while( fscanf(stdin, "%c", &b) != EOF )
  {
    /* lu[b] has pattern values that not match with input b */
    doStats(lu[b], stats);
  }
  printStats(stats);

  return 0;
}


void doStats(const uint8_t * const noBitMatch, uint32_t * const stats)
{
  uint8_t i, j = 0;

  if(noBitMatch)
  {
    for(i = 0; noBitMatch[i] != 0; i++)
      for(; j < SZ; j++)
        if( noBitMatch[i] == patList[j] )
        {
          stats[j]++;
          break;
        }
  }
  else
    stats[SZ]++;

}


void printStats(const uint32_t * const stats)
{
  const uint8_t * const patList = lu[0];
  uint8_t i;

  printf("Stats: \n");
  for(i = 0; i < SZ; i++)
    printf("  %3i%-3c%9i\n", patList[i], ':', stats[i]);
  printf("  ---%-3c%9i\n", ':', stats[SZ]);
}

loop version:

#include "pl.h"
#include <stdio.h>
#include <stdint.h>
#include <string.h>


void getNoBitMatch(const uint8_t, uint8_t * const);
void doStats(const uint8_t * const, uint32_t * const);
void printStats(const uint32_t * const);


int main(void)
{
  uint8_t b;
  uint8_t noBitMatch[SZ];
  uint32_t stats[SZ + 1] = { 0 };

  while( fscanf(stdin, "%c", &b ) != EOF )
  {     
    getNoBitMatch(b, noBitMatch);
    doStats(noBitMatch, stats); 
  }
  printStats(stats);

  return 0;
}


void doStats(const uint8_t * const noBitMatch, uint32_t * const stats)
{
  uint32_t i;
  uint8_t f;

  for(i = 0, f = 0; i < SZ; i++)
  {
    f = ( (noBitMatch[i]) ? 1 : f );    
    stats[i] += noBitMatch[i];
  }

  stats[SZ] += (f) ? 0 : 1;
}


void getNoBitMatch(const uint8_t b, uint8_t * const noBitMatch)
{
  uint8_t i;

  for(i = 0; i < SZ; i++)
    noBitMatch[i] = ( (b & patList[i]) == 0 ) ? 1 : 0;
}


void printStats(const uint32_t * const stats)
{
  uint8_t i;

  printf("Stats: \n");
  for(i = 0; i < SZ; i++)
    printf("  %3i%-3c%9i\n", patList[i], ':', stats[i]);
  printf("  ---%-3c%9i\n", ':', stats[SZ]);
}

Both code perform same action: count bytes that not match with a concrete byte of pattern list (pl.h).

Makefile for compile them:

###

CC = gcc
CFLAGS = -c -Wall
SPDUP = -O3
DEBUG = -ggdb3 -O0
EXECUTABLE = noloop
AUXEXEC = loop

LU_SCRIPT = ./lup.py
LU_HEADER = lu.h
LU_PATLIST_HEADER = pl.h

#LU_PATLIST = -p "{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }"
#LU_PATLIST = -p "{ 3, 6, 12, 15, 32, 48, 69, 254 }"
LU_PATLIST = -p "{ 3, 6, 12, 48 }"
#LU_PATLIST = -p "{ 1, 2 }"
#LU_PATLIST = -p "{ 1 }"
LU_FILE = -l $(LU_HEADER)
LU_PAT_FILE = -f $(LU_PATLIST_HEADER)


SRC= noloop.c loop.c

SOURCE = $(EXECUTABLE).c
OBJECTS = $(SOURCE:.c=.o)

AUXSRC = $(AUXEXEC).c
AUXOBJ = $(AUXSRC:.c=.o)


all: $(EXECUTABLE) $(AUXEXEC)

lookup:
    $(LU_SCRIPT) $(LU_PATLIST) $(LU_FILE) $(LU_PAT_FILE)
    touch $(SRC)

$(EXECUTABLE): lookup $(OBJECTS)
    $(CC) $(OBJECTS) -o $@

$(AUXEXEC): $(AUXOBJ)
    $(CC) $(AUXOBJ) -o $@

.c.o:
    $(CC) $(CFLAGS) $(SPDUP) -c $<

debug: lookup dbg
    $(CC) $(OBJECTS) -o $(EXECUTABLE)
    $(CC) $(AUXOBJ) -o $(AUXEXEC)

dbg: *.c
    $(CC) $(CFLAGS) $(DEBUG) -c $<

clean:
    rm -f $(EXECUTABLE) $(AUXEXEC) *.o &> /dev/null

.PHONY: clean

I've use three plain texts as input stream: gpl v3 plain text, Holy Bible plain text and linux kernel sources using recursive cat tool.
Executing this code with different pattern list give me this results:

Sat Sep 24 15:03:18 CEST 2011


 Test1:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:      18917
    2:      22014
    3:      12423
    4:      19015
    5:      11111
    6:      12647
    7:       7791
    8:      23498
    9:      13637
   10:      16032
   11:       9997
   12:      14059
   13:       9225
   14:       8609
   15:       6629
   16:      25610
  ---:          0

real    0m0.016s
user    0m0.008s
sys     0m0.016s

 Loop version:
------------------------
Stats: 
    1:      18917
    2:      22014
    3:      12423
    4:      19015
    5:      11111
    6:      12647
    7:       7791
    8:      23498
    9:      13637
   10:      16032
   11:       9997
   12:      14059
   13:       9225
   14:       8609
   15:       6629
   16:      25610
  ---:          0

real    0m0.020s
user    0m0.020s
sys     0m0.008s


 Test2:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:    3392095
    2:    3970343
    3:    2325421
    4:    3102869
    5:    1973137
    6:    2177366
    7:    1434363
    8:    3749010
    9:    2179167
   10:    2751134
   11:    1709076
   12:    2137823
   13:    1386038
   14:    1466132
   15:    1072405
   16:    4445367
  ---:       3310

real    0m1.048s
user    0m1.044s
sys     0m0.012s

 Loop version:
------------------------
Stats: 
    1:    3392095
    2:    3970343
    3:    2325421
    4:    3102869
    5:    1973137
    6:    2177366
    7:    1434363
    8:    3749010
    9:    2179167
   10:    2751134
   11:    1709076
   12:    2137823
   13:    1386038
   14:    1466132
   15:    1072405
   16:    4445367
  ---:       3310

real    0m0.926s
user    0m0.924s
sys     0m0.016s


 Test3:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:  222678565
    2:  254789058
    3:  137364784
    4:  239010012
    5:  133131414
    6:  146334792
    7:   83232971
    8:  246531446
    9:  145867949
   10:  161728907
   11:  103142808
   12:  147836792
   13:   93927370
   14:   87122985
   15:   66624721
   16:  275921653
  ---:   16845505

real    2m22.900s
user    3m43.686s
sys     1m14.613s

 Loop version:
------------------------
Stats: 
    1:  222678565
    2:  254789058
    3:  137364784
    4:  239010012
    5:  133131414
    6:  146334792
    7:   83232971
    8:  246531446
    9:  145867949
   10:  161728907
   11:  103142808
   12:  147836792
   13:   93927370
   14:   87122985
   15:   66624721
   16:  275921653
  ---:   16845505

real    2m42.560s
user    3m56.011s
sys     1m26.037s


 Test4:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:      12423
    6:      12647
   12:      14059
   15:       6629
   32:       2338
   48:       1730
   69:       6676
  254:          0
  ---:      11170

real    0m0.011s
user    0m0.004s
sys     0m0.016s

 Loop version:
------------------------
Stats: 
    3:      12423
    6:      12647
   12:      14059
   15:       6629
   32:       2338
   48:       1730
   69:       6676
  254:          0
  ---:      11170

real    0m0.021s
user    0m0.020s
sys     0m0.008s


 Test5:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:    2325421
    6:    2177366
   12:    2137823
   15:    1072405
   32:     425404
   48:     397564
   69:    1251668
  254:          0
  ---:    1781959

real    0m0.969s
user    0m0.936s
sys     0m0.048s

 Loop version:
------------------------
Stats: 
    3:    2325421
    6:    2177366
   12:    2137823
   15:    1072405
   32:     425404
   48:     397564
   69:    1251668
  254:          0
  ---:    1781959

real    0m1.447s
user    0m1.424s
sys     0m0.032s


 Test6:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:  137364784
    6:  146334792
   12:  147836792
   15:   66624721
   32:   99994388
   48:   64451562
   69:   89249942
  254:       5712
  ---:  105210728

real    2m38.851s
user    3m37.510s
sys     1m26.653s

 Loop version:
------------------------
Stats: 
    3:  137364784
    6:  146334792
   12:  147836792
   15:   66624721
   32:   99994388
   48:   64451562
   69:   89249942
  254:       5712
  ---:  105210728

real    2m32.041s
user    3m36.022s
sys     1m27.393s


 Test7:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:      12423
    6:      12647
   12:      14059
   48:       1730
  ---:      11277

real    0m0.013s
user    0m0.016s
sys     0m0.004s

 Loop version:
------------------------
Stats: 
    3:      12423
    6:      12647
   12:      14059
   48:       1730
  ---:      11277

real    0m0.014s
user    0m0.020s
sys     0m0.000s


 Test8:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:    2325421
    6:    2177366
   12:    2137823
   48:     397564
  ---:    1850018

real    0m0.933s
user    0m0.916s
sys     0m0.036s

 Loop version:
------------------------
Stats: 
    3:    2325421
    6:    2177366
   12:    2137823
   48:     397564
  ---:    1850018

real    0m0.892s
user    0m0.860s
sys     0m0.052s


 Test9:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:  137364784
    6:  146334792
   12:  147836792
   48:   64451562
  ---:  132949214

real    2m31.187s
user    3m31.289s
sys     1m25.909s

 Loop version:
------------------------
Stats: 
    3:  137364784
    6:  146334792
   12:  147836792
   48:   64451562
  ---:  132949214

real    2m34.942s
user    3m33.081s
sys     1m24.381s


 Test10:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:      18917
    2:      22014
  ---:       6639

real    0m0.014s
user    0m0.016s
sys     0m0.008s

 Loop version:
------------------------
Stats: 
    1:      18917
    2:      22014
  ---:       6639

real    0m0.017s
user    0m0.016s
sys     0m0.008s


 Test11:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:    3392095
    2:    3970343
  ---:     881222

real    0m0.861s
user    0m0.848s
sys     0m0.032s

 Loop version:
------------------------
Stats: 
    1:    3392095
    2:    3970343
  ---:     881222

real    0m0.781s
user    0m0.760s
sys     0m0.044s


 Test12:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:  222678565
    2:  254789058
  ---:   84476465

real    2m29.894s
user    3m30.449s
sys     1m23.177s

 Loop version:
------------------------
Stats: 
    1:  222678565
    2:  254789058
  ---:   84476465

real    2m21.103s
user    3m22.321s
sys     1m24.001s


 Test13:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:      18917
  ---:      16230

real    0m0.015s
user    0m0.020s
sys     0m0.008s

 Loop version:
------------------------
Stats: 
    1:      18917
  ---:      16230

real    0m0.016s
user    0m0.016s
sys     0m0.008s


 Test14:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:    3392095
  ---:    2526144

real    0m0.811s
user    0m0.808s
sys     0m0.024s

 Loop version:
------------------------
Stats: 
    1:    3392095
  ---:    2526144

real    0m0.709s
user    0m0.688s
sys     0m0.040s


 Test15:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:  222678565
  ---:  201900739

real    2m21.510s
user    3m23.009s
sys     1m23.861s

 Loop version:
------------------------
Stats: 
    1:  222678565
  ---:  201900739

real    2m22.677s
user    3m26.477s
sys     1m23.385s


Sat Sep 24 15:28:28 CEST 2011

Conclusions:

In my opinion, use of a look up table improve code execution by increasing code size, but that improvment are not too much significant. To start to notice differences, the amount input bytes should be huge.