Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/openssh/src/bitmap.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | /* $OpenBSD: bitmap.c,v 1.9 2017/10/20 01:56:39 djm Exp $ */ | - | ||||||||||||||||||
2 | /* | - | ||||||||||||||||||
3 | * Copyright (c) 2015 Damien Miller <djm@mindrot.org> | - | ||||||||||||||||||
4 | * | - | ||||||||||||||||||
5 | * Permission to use, copy, modify, and distribute this software for any | - | ||||||||||||||||||
6 | * purpose with or without fee is hereby granted, provided that the above | - | ||||||||||||||||||
7 | * copyright notice and this permission notice appear in all copies. | - | ||||||||||||||||||
8 | * | - | ||||||||||||||||||
9 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | - | ||||||||||||||||||
10 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | - | ||||||||||||||||||
11 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | - | ||||||||||||||||||
12 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | - | ||||||||||||||||||
13 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | - | ||||||||||||||||||
14 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | - | ||||||||||||||||||
15 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | - | ||||||||||||||||||
16 | */ | - | ||||||||||||||||||
17 | - | |||||||||||||||||||
18 | #include "includes.h" | - | ||||||||||||||||||
19 | - | |||||||||||||||||||
20 | #include <sys/types.h> | - | ||||||||||||||||||
21 | #include <string.h> | - | ||||||||||||||||||
22 | #include <stdlib.h> | - | ||||||||||||||||||
23 | - | |||||||||||||||||||
24 | #include "bitmap.h" | - | ||||||||||||||||||
25 | - | |||||||||||||||||||
26 | #define BITMAP_WTYPE u_int | - | ||||||||||||||||||
27 | #define BITMAP_MAX (1<<24) | - | ||||||||||||||||||
28 | #define BITMAP_BYTES (sizeof(BITMAP_WTYPE)) | - | ||||||||||||||||||
29 | #define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8) | - | ||||||||||||||||||
30 | #define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1) | - | ||||||||||||||||||
31 | struct bitmap { | - | ||||||||||||||||||
32 | BITMAP_WTYPE *d; | - | ||||||||||||||||||
33 | size_t len; /* number of words allocated */ | - | ||||||||||||||||||
34 | size_t top; /* index of top word allocated */ | - | ||||||||||||||||||
35 | }; | - | ||||||||||||||||||
36 | - | |||||||||||||||||||
37 | struct bitmap * | - | ||||||||||||||||||
38 | bitmap_new(void) | - | ||||||||||||||||||
39 | { | - | ||||||||||||||||||
40 | struct bitmap *ret; | - | ||||||||||||||||||
41 | - | |||||||||||||||||||
42 | if ((ret = calloc(1, sizeof(*ret))) == NULL)
| 0-1 | ||||||||||||||||||
43 | return NULL; never executed: return ((void *)0) ; | 0 | ||||||||||||||||||
44 | if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
| 0-1 | ||||||||||||||||||
45 | free(ret); | - | ||||||||||||||||||
46 | return NULL; never executed: return ((void *)0) ; | 0 | ||||||||||||||||||
47 | } | - | ||||||||||||||||||
48 | ret->len = 1; | - | ||||||||||||||||||
49 | ret->top = 0; | - | ||||||||||||||||||
50 | return ret; executed 1 time by 1 test: return ret; Executed by:
| 1 | ||||||||||||||||||
51 | } | - | ||||||||||||||||||
52 | - | |||||||||||||||||||
53 | void | - | ||||||||||||||||||
54 | bitmap_free(struct bitmap *b) | - | ||||||||||||||||||
55 | { | - | ||||||||||||||||||
56 | if (b != NULL && b->d != NULL) {
| 0-1 | ||||||||||||||||||
57 | bitmap_zero(b); | - | ||||||||||||||||||
58 | free(b->d); | - | ||||||||||||||||||
59 | b->d = NULL; | - | ||||||||||||||||||
60 | } executed 1 time by 1 test: end of block Executed by:
| 1 | ||||||||||||||||||
61 | free(b); | - | ||||||||||||||||||
62 | } executed 1 time by 1 test: end of block Executed by:
| 1 | ||||||||||||||||||
63 | - | |||||||||||||||||||
64 | void | - | ||||||||||||||||||
65 | bitmap_zero(struct bitmap *b) | - | ||||||||||||||||||
66 | { | - | ||||||||||||||||||
67 | memset(b->d, 0, b->len * BITMAP_BYTES); | - | ||||||||||||||||||
68 | b->top = 0; | - | ||||||||||||||||||
69 | } executed 6899905 times by 1 test: end of block Executed by:
| 6899905 | ||||||||||||||||||
70 | - | |||||||||||||||||||
71 | int | - | ||||||||||||||||||
72 | bitmap_test_bit(struct bitmap *b, u_int n) | - | ||||||||||||||||||
73 | { | - | ||||||||||||||||||
74 | if (b->top >= b->len)
| 0-903887424 | ||||||||||||||||||
75 | return 0; /* invalid */ never executed: return 0; | 0 | ||||||||||||||||||
76 | if (b->len == 0 || (n / BITMAP_BITS) > b->top)
| 0-903887424 | ||||||||||||||||||
77 | return 0; executed 91167192 times by 1 test: return 0; Executed by:
| 91167192 | ||||||||||||||||||
78 | return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1; executed 812720232 times by 1 test: return (b->d[n / (sizeof(u_int) * 8)] >> (n & ((u_int)(sizeof(u_int) * 8) - 1))) & 1; Executed by:
| 812720232 | ||||||||||||||||||
79 | } | - | ||||||||||||||||||
80 | - | |||||||||||||||||||
81 | static int | - | ||||||||||||||||||
82 | reserve(struct bitmap *b, u_int n) | - | ||||||||||||||||||
83 | { | - | ||||||||||||||||||
84 | BITMAP_WTYPE *tmp; | - | ||||||||||||||||||
85 | size_t nlen; | - | ||||||||||||||||||
86 | - | |||||||||||||||||||
87 | if (b->top >= b->len || n > BITMAP_MAX)
| 0-310443408 | ||||||||||||||||||
88 | return -1; /* invalid */ never executed: return -1; | 0 | ||||||||||||||||||
89 | nlen = (n / BITMAP_BITS) + 1; | - | ||||||||||||||||||
90 | if (b->len < nlen) {
| 4-310443404 | ||||||||||||||||||
91 | if ((tmp = recallocarray(b->d, b->len,
| 0-4 | ||||||||||||||||||
92 | nlen, BITMAP_BYTES)) == NULL)
| 0-4 | ||||||||||||||||||
93 | return -1; never executed: return -1; | 0 | ||||||||||||||||||
94 | b->d = tmp; | - | ||||||||||||||||||
95 | b->len = nlen; | - | ||||||||||||||||||
96 | } executed 4 times by 1 test: end of block Executed by:
| 4 | ||||||||||||||||||
97 | return 0; executed 310443408 times by 1 test: return 0; Executed by:
| 310443408 | ||||||||||||||||||
98 | } | - | ||||||||||||||||||
99 | - | |||||||||||||||||||
100 | int | - | ||||||||||||||||||
101 | bitmap_set_bit(struct bitmap *b, u_int n) | - | ||||||||||||||||||
102 | { | - | ||||||||||||||||||
103 | int r; | - | ||||||||||||||||||
104 | size_t offset; | - | ||||||||||||||||||
105 | - | |||||||||||||||||||
106 | if ((r = reserve(b, n)) != 0)
| 0-308143440 | ||||||||||||||||||
107 | return r; never executed: return r; | 0 | ||||||||||||||||||
108 | offset = n / BITMAP_BITS; | - | ||||||||||||||||||
109 | if (offset > b->top)
| 6490723-301652717 | ||||||||||||||||||
110 | b->top = offset; executed 6490723 times by 1 test: b->top = offset; Executed by:
| 6490723 | ||||||||||||||||||
111 | b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK); | - | ||||||||||||||||||
112 | return 0; executed 308143440 times by 1 test: return 0; Executed by:
| 308143440 | ||||||||||||||||||
113 | } | - | ||||||||||||||||||
114 | - | |||||||||||||||||||
115 | /* Resets b->top to point to the most significant bit set in b->d */ | - | ||||||||||||||||||
116 | static void | - | ||||||||||||||||||
117 | retop(struct bitmap *b) | - | ||||||||||||||||||
118 | { | - | ||||||||||||||||||
119 | if (b->top >= b->len)
| 0-18347471 | ||||||||||||||||||
120 | return; never executed: return; | 0 | ||||||||||||||||||
121 | while (b->top > 0 && b->d[b->top] == 0)
| 6-18167793 | ||||||||||||||||||
122 | b->top--; executed 6 times by 1 test: b->top--; Executed by:
| 6 | ||||||||||||||||||
123 | } executed 18347471 times by 1 test: end of block Executed by:
| 18347471 | ||||||||||||||||||
124 | - | |||||||||||||||||||
125 | void | - | ||||||||||||||||||
126 | bitmap_clear_bit(struct bitmap *b, u_int n) | - | ||||||||||||||||||
127 | { | - | ||||||||||||||||||
128 | size_t offset; | - | ||||||||||||||||||
129 | - | |||||||||||||||||||
130 | if (b->top >= b->len || n > BITMAP_MAX)
| 0-6847632 | ||||||||||||||||||
131 | return; /* invalid */ never executed: return; | 0 | ||||||||||||||||||
132 | offset = n / BITMAP_BITS; | - | ||||||||||||||||||
133 | if (offset > b->top)
| 0-6847632 | ||||||||||||||||||
134 | return; never executed: return; | 0 | ||||||||||||||||||
135 | b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK)); | - | ||||||||||||||||||
136 | /* The top may have changed as a result of the clear */ | - | ||||||||||||||||||
137 | retop(b); | - | ||||||||||||||||||
138 | } executed 6847632 times by 1 test: end of block Executed by:
| 6847632 | ||||||||||||||||||
139 | - | |||||||||||||||||||
140 | size_t | - | ||||||||||||||||||
141 | bitmap_nbits(struct bitmap *b) | - | ||||||||||||||||||
142 | { | - | ||||||||||||||||||
143 | size_t bits; | - | ||||||||||||||||||
144 | BITMAP_WTYPE w; | - | ||||||||||||||||||
145 | - | |||||||||||||||||||
146 | retop(b); | - | ||||||||||||||||||
147 | if (b->top >= b->len)
| 0-9199872 | ||||||||||||||||||
148 | return 0; /* invalid */ never executed: return 0; | 0 | ||||||||||||||||||
149 | if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
| 0-9199872 | ||||||||||||||||||
150 | return 0; executed 4 times by 1 test: return 0; Executed by:
| 4 | ||||||||||||||||||
151 | /* Find MSB set */ | - | ||||||||||||||||||
152 | w = b->d[b->top]; | - | ||||||||||||||||||
153 | bits = (b->top + 1) * BITMAP_BITS; | - | ||||||||||||||||||
154 | while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
| 9199868-134459152 | ||||||||||||||||||
155 | w <<= 1; | - | ||||||||||||||||||
156 | bits--; | - | ||||||||||||||||||
157 | } executed 134459152 times by 1 test: end of block Executed by:
| 134459152 | ||||||||||||||||||
158 | return bits; executed 9199868 times by 1 test: return bits; Executed by:
| 9199868 | ||||||||||||||||||
159 | } | - | ||||||||||||||||||
160 | - | |||||||||||||||||||
161 | size_t | - | ||||||||||||||||||
162 | bitmap_nbytes(struct bitmap *b) | - | ||||||||||||||||||
163 | { | - | ||||||||||||||||||
164 | return (bitmap_nbits(b) + 7) / 8; executed 6899904 times by 1 test: return (bitmap_nbits(b) + 7) / 8; Executed by:
| 6899904 | ||||||||||||||||||
165 | } | - | ||||||||||||||||||
166 | - | |||||||||||||||||||
167 | int | - | ||||||||||||||||||
168 | bitmap_to_string(struct bitmap *b, void *p, size_t l) | - | ||||||||||||||||||
169 | { | - | ||||||||||||||||||
170 | u_char *s = (u_char *)p; | - | ||||||||||||||||||
171 | size_t i, j, k, need = bitmap_nbytes(b); | - | ||||||||||||||||||
172 | - | |||||||||||||||||||
173 | if (l < need || b->top >= b->len)
| 0-2299968 | ||||||||||||||||||
174 | return -1; never executed: return -1; | 0 | ||||||||||||||||||
175 | if (l > need)
| 0-2299968 | ||||||||||||||||||
176 | l = need; executed 2299968 times by 1 test: l = need; Executed by:
| 2299968 | ||||||||||||||||||
177 | /* Put the bytes from LSB backwards */ | - | ||||||||||||||||||
178 | for (i = k = 0; i < b->top + 1; i++) {
| 2299968-8129916 | ||||||||||||||||||
179 | for (j = 0; j < BITMAP_BYTES; j++) {
| 6522524-30946383 | ||||||||||||||||||
180 | if (k >= l)
| 1607392-29338991 | ||||||||||||||||||
181 | break; executed 1607392 times by 1 test: break; Executed by:
| 1607392 | ||||||||||||||||||
182 | s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff; | - | ||||||||||||||||||
183 | } executed 29338991 times by 1 test: end of block Executed by:
| 29338991 | ||||||||||||||||||
184 | } executed 8129916 times by 1 test: end of block Executed by:
| 8129916 | ||||||||||||||||||
185 | return 0; executed 2299968 times by 1 test: return 0; Executed by:
| 2299968 | ||||||||||||||||||
186 | } | - | ||||||||||||||||||
187 | - | |||||||||||||||||||
188 | int | - | ||||||||||||||||||
189 | bitmap_from_string(struct bitmap *b, const void *p, size_t l) | - | ||||||||||||||||||
190 | { | - | ||||||||||||||||||
191 | int r; | - | ||||||||||||||||||
192 | size_t i, offset, shift; | - | ||||||||||||||||||
193 | const u_char *s = (const u_char *)p; | - | ||||||||||||||||||
194 | - | |||||||||||||||||||
195 | if (l > BITMAP_MAX / 8)
| 0-2299968 | ||||||||||||||||||
196 | return -1; never executed: return -1; | 0 | ||||||||||||||||||
197 | if ((r = reserve(b, l * 8)) != 0)
| 0-2299968 | ||||||||||||||||||
198 | return r; never executed: return r; | 0 | ||||||||||||||||||
199 | bitmap_zero(b); | - | ||||||||||||||||||
200 | if (l == 0)
| 1-2299967 | ||||||||||||||||||
201 | return 0; executed 1 time by 1 test: return 0; Executed by:
| 1 | ||||||||||||||||||
202 | b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1; | - | ||||||||||||||||||
203 | shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8; | - | ||||||||||||||||||
204 | for (i = 0; i < l; i++) {
| 2299967-29338991 | ||||||||||||||||||
205 | b->d[offset] |= (BITMAP_WTYPE)s[i] << shift; | - | ||||||||||||||||||
206 | if (shift == 0) {
| 8129915-21209076 | ||||||||||||||||||
207 | offset--; | - | ||||||||||||||||||
208 | shift = BITMAP_BITS - 8; | - | ||||||||||||||||||
209 | } else executed 8129915 times by 1 test: end of block Executed by:
| 8129915 | ||||||||||||||||||
210 | shift -= 8; executed 21209076 times by 1 test: shift -= 8; Executed by:
| 21209076 | ||||||||||||||||||
211 | } | - | ||||||||||||||||||
212 | retop(b); | - | ||||||||||||||||||
213 | return 0; executed 2299967 times by 1 test: return 0; Executed by:
| 2299967 | ||||||||||||||||||
214 | } | - | ||||||||||||||||||
Source code | Switch to Preprocessed file |