jharkins@sagpd1.UUCP (Jim Harkins) (05/26/90)
I need to implement what I think of as a sliding window over a long string of bits. I have a bitmap spread across several words and I need to find a set of N adjacent bits that are set, and it should easily cross word boundries. In other words, not only are bits 4 and 5 of word 0 adjacent, so are bits 31 of word 0 and bit 0 of word 1. My string of N adjacent bits can be up to 16 bits long, and the bitmap will probably be about 20 words long (at 32 bits per word, but portability would be nice). It's perfectly OK to look for the string in whole words before going back to span edges. That is, if word 0 is AAAA and word 1 is 5555 then it's ok to look for 2 adjacent bits in word 0, then word 1, then the boundry between the words. I think this kind of thing is used a lot in bit mapped graphics, so does anyone have an algorithm or pointer to an algorithm I can use? I'm running C on a 68000 chip, but portability would be nice. Thanks in advance. -- jim jharkins@sagpd1 I *still* don't know who killed Laura Palmer!
simon.ewins@f664.n250.z1.fidonet.org (simon ewins) (06/01/90)
> From: jharkins@sagpd1.UUCP (Jim Harkins) > Orga: Scientific Atlanta-GPD, San Diego > > I need to implement what I think of as a sliding window over a long > string of bits. I have a bitmap spread across several words and I > need to find a set of N adjacent bits that are set, I have had good success with this... You can adjust as needed but the idea should work as it has for me. The following code can handle bit- arrays of any length. #include <stdio.h> #define SET 1 #define CLR 2 #define GET 3 main() { unsigned char bit_array[8]; int i; /* ** clear the array to 0's */ for(i=0;i<8;i++) bit_array[i]=NULL; /* ** show bit 23 on/off Off ** set bit 23 on ** show bit 23 on/off On ** show bit 22 on/off Off ** show bit 24 on/off Off ** set bit 24 on ** show bit 24 on/off On ** set bit 24 off ** show bit 24 on/off Off ** ** etc. etc. etc... */ printf("Bit 23: %s\n",bit(GET,23,bit_array) ? "On" : "Off"); bit(SET,23,bit_array); printf("Bit 23: %s\n",bit(GET,23,bit_array) ? "On" : "Off"); printf("Bit 22: %s\n",bit(GET,22,bit_array) ? "On" : "Off"); printf("Bit 24: %s\n",bit(GET,24,bit_array) ? "On" : "Off"); bit(SET,24,bit_array); printf("Bit 24: %s\n",bit(GET,24,bit_array) ? "On" : "Off"); bit(CLR,24,bit_array); printf("Bit 24: %s\n",bit(GET,24,bit_array) ? "On" : "Off"); } /* ** set, get or clear bit in a character array ... This is NOT range checked ** ... garbage in, garbage out ... so make sure that the bit number is in ** the range of the size of the character array * 8 AND that the action is ** only one of GET, SET, or CLR */ bit(action,bit_pos,array) unsigned char array[]; int action; int bit_pos; { unsigned char test_val; int index; index=bit_pos/8; /* element of array to test */ switch(bit_pos%8) { /* bit in indexth element to get, set, or clear */ case 0: test_val=0x01; break; case 1: test_val=0x02; break; case 2: test_val=0x04; break; case 3: test_val=0x08; break; case 4: test_val=0x10; break; case 5: test_val=0x20; break; case 6: test_val=0x40; break; case 7: test_val=0x80; break; } switch(action) { case GET: if((array[index]&test_val)==test_val) return(TRUE); return(FALSE); case SET: array[index]|=test_val; return(TRUE); case CLR: array[index]&=(0xff-test_val); return(FALSE); } } /* end */ --- D'Bridge 1.30/002506 * Origin: A_X_A_X_A [ FactBase/qDos <> 416-483-2821 ] (1:250/664)
rsalz@bbn.com (Rich Salz) (06/02/90)
Someone posted the following code: >{ > unsigned char test_val; > int index; > > index=bit_pos/8; /* element of array to test */ > switch(bit_pos%8) { /* bit in indexth element to get, set, or clear */ > case 0: test_val=0x01; break; > case 1: test_val=0x02; break; > case 2: test_val=0x04; break; > case 3: test_val=0x08; break; > case 4: test_val=0x10; break; > case 5: test_val=0x20; break; > case 6: test_val=0x40; break; > case 7: test_val=0x80; break; > } > switch(action) { > case GET: > if((array[index]&test_val)==test_val) > return(TRUE); > return(FALSE); > case SET: > array[index]|=test_val; > return(TRUE); > case CLR: > array[index]&=(0xff-test_val); > return(FALSE); > } >} I think this is better. Style aside, it avoids the gross unportability used in the CLR case, and the switch used to set test_val. index = bit_pos >> 3; test_val = 1 << (bit_pos & 7); switch (action) { case GET: return array[index] & test_val; case SET: array[index] |= test_value; break; case CLR: array[index] &= ~test_val; break; } return TRUE; If you're doing general bitmap stuff, you're probably best off turning the above routine into speciale-purpose macros, like the BSD fdset stuff, or setbit/clrbit in <sys/param.h>: #define setbit(a,i) ((a)[(i)/NBBY] |= 1<<((i)%NBBY)) #define clrbit(a,i) ((a)[(i)/NBBY] &= ~(1<<((i)%NBBY))) #define isset(a,i) ((a)[(i)/NBBY] & (1<<((i)%NBBY))) #define isclr(a,i) (((a)[(i)/NBBY] & (1<<((i)%NBBY))) == 0) NBBY is the number of bits in a byte, and is typically 8, so #define setbit(a,i) ((a)[(i) >> 3] |= 1<<((i) & 7)) #define clrbit(a,i) ((a)[(i) >> 3] &= ~(1<<((i) & 7))) #define isset(a,i) ((a)[(i) >> 3] & (1<<((i) & 7))) #define isclr(a,i) (((a)[(i) >> 3] & (1<<((i) & 7))) == 0) -- Please send comp.sources.unix-related mail to rsalz@uunet.uu.net. Use a domain-based address or give alternate paths, or you may lose out.