J
jacob navia
Here is a function to do the equivalent of strstr with bitstrings.
The basic ideas is to prepare a table of shifted patterns, and compare
bytes instead of bits, what makes things faster and easier.
I would like to thank Mr Morris Keesan and Mr Peter Nilsson of this discussion
group for their help with the bit shifting.
I present this function for you to shake it. Please try to find bugs,
inconsistencies or things that could be written better.
Thanks in advance for your help
-------------------------------------------------------------------bitstrstr.c
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
static unsigned char mask[] = { 255,127,63,31,15,7,3,1};
static unsigned char maskI[]= { 255,1,3,7,15,31,63,127};
/*------------------------------------------------------------------------
Procedure: bitBitstr ID:1
Purpose: Finds the bit position of the given bit-pattern in
the given text. The algorithm is as follows:
(1) It builds a table of CHAR_BIT lines, each line
holding a one bit right shifted pattern.
(2) For each byte in the text it will compare the
byte with each byte in the shifted pattern table. A
match is found if all bytes are equal.
(3) The first byte and the last byte must be masked
because they contain some bit positions with unused
bits.
Input: The bit-string to be searched and its length, and
the bit-pattern and its length. Both lengths in bits
Output: Zero if the pattern isn't found, or 1+bit-index of
the starting bit of the pattern if the pattern is
found.
Errors: If there is no memory it will return "pattern not
found" (zero).
------------------------------------------------------------------------*/
size_t bitBitstr(unsigned char *text,size_t textSize,unsigned char *pat,size_t patSize)
{
size_t patByteLength = (patSize+CHAR_BIT-1)/CHAR_BIT;
size_t i,j,k,stop;
unsigned char *ShiftTable,*ptable,*pText;
if (patSize > textSize) /* eliminate wrong arguments */
return 0;
/* Allocate the shift table. If no memory abort with zero. */
ShiftTable = calloc(patByteLength,CHAR_BIT);
if (ShiftTable == NULL) {
return 0;
}
/* The first line of the shift table is unshifted. Just copy it */
memcpy(ShiftTable,pat,patByteLength);
ptable = ShiftTable + patByteLength; /* Advance poinbter to next line */
for (i=1; i<CHAR_BIT; i++) {
/* Copy the last line into the new line */
memcpy(ptable,ptable-patByteLength,patByteLength);
/* Now shift it by one bit */
k=patByteLength;
for (j = 0; k--; ptable++) {
j = (j << CHAR_BIT) | *ptable;
*ptable = j >> 1;
}
}
/* We should stop when the number of bytes left is less than the pattern length */
stop = (textSize+CHAR_BIT-1)/CHAR_BIT - patByteLength;
/* For each byte in the input text */
for (k=0; k <= stop; k++) {
/* For each line in the shift table */
for (i=0; i<CHAR_BIT;i++) {
ptable = ShiftTable+i*patByteLength; /* will point to the table line */
pText = text+k; /* Will point at the current start character in the text */
/* The first character needs a mask since there could be
unused bits */
if ((*pText++ & mask) != *ptable++)
break;
/* Search each byte in the input text until last byte minus 1 */
for (j=1; j<patByteLength-1; j++) {
if (*pText++ != *ptable++)
break;
}
if (j == patByteLength-1) {
/* Test the last byte with the complemented mask */
if ((*pText & maskI[patSize&(CHAR_BIT-1)]) == *ptable) {
free(ShiftTable);
return 1+(k*CHAR_BIT)+i;
}
}
}
}
/* There was no match */
free(ShiftTable);
return 0;
}
#ifdef TEST
#include <stdio.h>
int main(void)
{
unsigned char *txt="\xfb\x1\x2\x3\x4\xba\xdb\xad\x5\x7\x2\x77";
unsigned char *pat="\xba\xdb\xad\x1";
size_t txtlen=12*CHAR_BIT;
size_t patlen=1+3*CHAR_BIT;
size_t result = bitBitstr(txt,txtlen,pat,patlen);
if (result != 41)
printf("failed (%u)\n",result);
}
#endif
The basic ideas is to prepare a table of shifted patterns, and compare
bytes instead of bits, what makes things faster and easier.
I would like to thank Mr Morris Keesan and Mr Peter Nilsson of this discussion
group for their help with the bit shifting.
I present this function for you to shake it. Please try to find bugs,
inconsistencies or things that could be written better.
Thanks in advance for your help
-------------------------------------------------------------------bitstrstr.c
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
static unsigned char mask[] = { 255,127,63,31,15,7,3,1};
static unsigned char maskI[]= { 255,1,3,7,15,31,63,127};
/*------------------------------------------------------------------------
Procedure: bitBitstr ID:1
Purpose: Finds the bit position of the given bit-pattern in
the given text. The algorithm is as follows:
(1) It builds a table of CHAR_BIT lines, each line
holding a one bit right shifted pattern.
(2) For each byte in the text it will compare the
byte with each byte in the shifted pattern table. A
match is found if all bytes are equal.
(3) The first byte and the last byte must be masked
because they contain some bit positions with unused
bits.
Input: The bit-string to be searched and its length, and
the bit-pattern and its length. Both lengths in bits
Output: Zero if the pattern isn't found, or 1+bit-index of
the starting bit of the pattern if the pattern is
found.
Errors: If there is no memory it will return "pattern not
found" (zero).
------------------------------------------------------------------------*/
size_t bitBitstr(unsigned char *text,size_t textSize,unsigned char *pat,size_t patSize)
{
size_t patByteLength = (patSize+CHAR_BIT-1)/CHAR_BIT;
size_t i,j,k,stop;
unsigned char *ShiftTable,*ptable,*pText;
if (patSize > textSize) /* eliminate wrong arguments */
return 0;
/* Allocate the shift table. If no memory abort with zero. */
ShiftTable = calloc(patByteLength,CHAR_BIT);
if (ShiftTable == NULL) {
return 0;
}
/* The first line of the shift table is unshifted. Just copy it */
memcpy(ShiftTable,pat,patByteLength);
ptable = ShiftTable + patByteLength; /* Advance poinbter to next line */
for (i=1; i<CHAR_BIT; i++) {
/* Copy the last line into the new line */
memcpy(ptable,ptable-patByteLength,patByteLength);
/* Now shift it by one bit */
k=patByteLength;
for (j = 0; k--; ptable++) {
j = (j << CHAR_BIT) | *ptable;
*ptable = j >> 1;
}
}
/* We should stop when the number of bytes left is less than the pattern length */
stop = (textSize+CHAR_BIT-1)/CHAR_BIT - patByteLength;
/* For each byte in the input text */
for (k=0; k <= stop; k++) {
/* For each line in the shift table */
for (i=0; i<CHAR_BIT;i++) {
ptable = ShiftTable+i*patByteLength; /* will point to the table line */
pText = text+k; /* Will point at the current start character in the text */
/* The first character needs a mask since there could be
unused bits */
if ((*pText++ & mask) != *ptable++)
break;
/* Search each byte in the input text until last byte minus 1 */
for (j=1; j<patByteLength-1; j++) {
if (*pText++ != *ptable++)
break;
}
if (j == patByteLength-1) {
/* Test the last byte with the complemented mask */
if ((*pText & maskI[patSize&(CHAR_BIT-1)]) == *ptable) {
free(ShiftTable);
return 1+(k*CHAR_BIT)+i;
}
}
}
}
/* There was no match */
free(ShiftTable);
return 0;
}
#ifdef TEST
#include <stdio.h>
int main(void)
{
unsigned char *txt="\xfb\x1\x2\x3\x4\xba\xdb\xad\x5\x7\x2\x77";
unsigned char *pat="\xba\xdb\xad\x1";
size_t txtlen=12*CHAR_BIT;
size_t patlen=1+3*CHAR_BIT;
size_t result = bitBitstr(txt,txtlen,pat,patlen);
if (result != 41)
printf("failed (%u)\n",result);
}
#endif