1 /*
2 * Copyright (c) 2018, Sam Kumar <samkumar@cs.berkeley.edu>
3 * Copyright (c) 2018, University of California, Berkeley
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the copyright holder nor the
14 * names of its contributors may be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 /* BITMAP */
31
32 #include <stdint.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "bitmap.h"
38
bmp_init(uint8_t * buf,size_t numbytes)39 void bmp_init(uint8_t* buf, size_t numbytes) {
40 memset(buf, 0x00, numbytes);
41 }
42
43 #define _bmp_getrangeinfo(buf, start, len, first_bit_id, first_byte_ptr, last_bit_id, last_byte_ptr) \
44 do { \
45 first_bit_id = (start & 0x7); \
46 first_byte_ptr = buf + (start >> 3); \
47 last_bit_id = (len & 0x7) + first_bit_id; \
48 last_byte_ptr = first_byte_ptr + (len >> 3) + (last_bit_id >> 3); \
49 last_bit_id &= 0x7; \
50 } while (0)
51
bmp_setrange(uint8_t * buf,size_t start,size_t len)52 void bmp_setrange(uint8_t* buf, size_t start, size_t len) {
53 uint8_t first_bit_id;
54 uint8_t* first_byte_set;
55 uint8_t last_bit_id;
56 uint8_t* last_byte_set;
57 uint8_t first_byte_mask, last_byte_mask;
58 _bmp_getrangeinfo(buf, start, len, first_bit_id, first_byte_set,
59 last_bit_id, last_byte_set);
60
61 first_byte_mask = (uint8_t) (0xFF >> first_bit_id);
62 last_byte_mask = (uint8_t) (0xFF << (8 - last_bit_id));
63
64 /* Set the bits. */
65 if (first_byte_set == last_byte_set) {
66 *first_byte_set |= (first_byte_mask & last_byte_mask);
67 } else {
68 *first_byte_set |= first_byte_mask;
69 memset(first_byte_set + 1, 0xFF, (size_t) (last_byte_set - first_byte_set - 1));
70 *last_byte_set |= last_byte_mask;
71 }
72 }
73
bmp_clrrange(uint8_t * buf,size_t start,size_t len)74 void bmp_clrrange(uint8_t* buf, size_t start, size_t len) {
75 uint8_t first_bit_id;
76 uint8_t* first_byte_clear;
77 uint8_t last_bit_id;
78 uint8_t* last_byte_clear;
79 uint8_t first_byte_mask, last_byte_mask;
80 _bmp_getrangeinfo(buf, start, len, first_bit_id, first_byte_clear,
81 last_bit_id, last_byte_clear);
82
83 first_byte_mask = (uint8_t) (0xFF << (8 - first_bit_id));
84 last_byte_mask = (uint8_t) (0xFF >> last_bit_id);
85
86 /* Clear the bits. */
87 if (first_byte_clear == last_byte_clear) {
88 *first_byte_clear &= (first_byte_mask | last_byte_mask);
89 } else {
90 *first_byte_clear &= first_byte_mask;
91 memset(first_byte_clear + 1, 0x00, (size_t) (last_byte_clear - first_byte_clear - 1));
92 *last_byte_clear &= last_byte_mask;
93 }
94 }
95
bmp_countset(uint8_t * buf,size_t buflen,size_t start,size_t limit)96 size_t bmp_countset(uint8_t* buf, size_t buflen, size_t start, size_t limit) {
97 uint8_t first_bit_id;
98 uint8_t first_byte;
99 uint8_t ideal_first_byte;
100 size_t numset;
101 uint8_t curr_byte;
102 size_t curr_index = start >> 3;
103 first_bit_id = start & 0x7;
104 first_byte = *(buf + curr_index);
105
106 numset = 8 - first_bit_id; // initialize optimistically, assuming that the first byte will have all 1's in the part we care about
107 ideal_first_byte = (uint8_t) (0xFF >> first_bit_id);
108 first_byte &= ideal_first_byte;
109 if (first_byte == ideal_first_byte) {
110 // All bits in the first byte starting at first_bit_id are set
111 for (curr_index = curr_index + 1; curr_index < buflen && numset < limit; curr_index++) {
112 curr_byte = buf[curr_index];
113 if (curr_byte == (uint8_t) 0xFF) {
114 numset += 8;
115 } else {
116 while (curr_byte & (uint8_t) 0x80) { // we could add a numset < limit check here, but it probably isn't worth it
117 curr_byte <<= 1;
118 numset++;
119 }
120 break;
121 }
122 }
123 } else {
124 // The streak ends within the first byte
125 do {
126 first_byte >>= 1;
127 ideal_first_byte >>= 1;
128 numset--;
129 } while (first_byte != ideal_first_byte);
130 }
131 return numset;
132 }
133
bmp_isempty(uint8_t * buf,size_t buflen)134 int bmp_isempty(uint8_t* buf, size_t buflen) {
135 uint8_t* bufend = buf + buflen;
136 while (buf < bufend) {
137 if (*(buf++)) {
138 return 0;
139 }
140 }
141 return 1;
142 }
143
144 /*
145 * This function is unused, but I'm leaving it in the code as a comment in case
146 * it becomes useful for debugging later on.
147 */
148 #if 0
149 void bmp_print(uint8_t* buf, size_t buflen) {
150 size_t i;
151 for (i = 0; i < buflen; i++) {
152 printf("%02X", buf[i]);
153 }
154 printf("\n");
155 }
156 #endif
157