Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/ssh/lib/../bitmap.c	Lines:	0	86	0.0 %
Date:	2017-11-13	Branches:	0	66	0.0 %


/* $OpenBSD: bitmap.c,v 1.9 2017/10/20 01:56:39 djm Exp $ */
/*
 * Copyright (c) 2015 Damien Miller <djm@mindrot.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/types.h>
#include <string.h>
#include <stdlib.h>

#include "bitmap.h"

#define BITMAP_WTYPE	u_int
#define BITMAP_MAX	(1<<24)
#define BITMAP_BYTES	(sizeof(BITMAP_WTYPE))
#define BITMAP_BITS	(sizeof(BITMAP_WTYPE) * 8)
#define BITMAP_WMASK	((BITMAP_WTYPE)BITMAP_BITS - 1)
struct bitmap {
	BITMAP_WTYPE *d;
	size_t len; /* number of words allocated */
	size_t top; /* index of top word allocated */
};

struct bitmap *
bitmap_new(void)
{
	struct bitmap *ret;

	if ((ret = calloc(1, sizeof(*ret))) == NULL)
		return NULL;
	if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
		free(ret);
		return NULL;
	}
	ret->len = 1;
	ret->top = 0;
	return ret;
}

void
bitmap_free(struct bitmap *b)
{
	if (b != NULL && b->d != NULL) {
		bitmap_zero(b);
		free(b->d);
		b->d = NULL;
	}
	free(b);
}

void
bitmap_zero(struct bitmap *b)
{
	memset(b->d, 0, b->len * BITMAP_BYTES);
	b->top = 0;
}

int
bitmap_test_bit(struct bitmap *b, u_int n)
{
	if (b->top >= b->len)
		return 0; /* invalid */
	if (b->len == 0 || (n / BITMAP_BITS) > b->top)
		return 0;
	return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
}

static int
reserve(struct bitmap *b, u_int n)
{
	BITMAP_WTYPE *tmp;
	size_t nlen;

	if (b->top >= b->len || n > BITMAP_MAX)
		return -1; /* invalid */
	nlen = (n / BITMAP_BITS) + 1;
	if (b->len < nlen) {
		if ((tmp = recallocarray(b->d, b->len,
		    nlen, BITMAP_BYTES)) == NULL)
			return -1;
		b->d = tmp;
		b->len = nlen;
	}
	return 0;
}

int
bitmap_set_bit(struct bitmap *b, u_int n)
{
	int r;
	size_t offset;

	if ((r = reserve(b, n)) != 0)
		return r;
	offset = n / BITMAP_BITS;
	if (offset > b->top)
		b->top = offset;
	b->d[offset] |= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
	return 0;
}

/* Resets b->top to point to the most significant bit set in b->d */
static void
retop(struct bitmap *b)
{
	if (b->top >= b->len)
		return;
	while (b->top > 0 && b->d[b->top] == 0)
		b->top--;
}

void
bitmap_clear_bit(struct bitmap *b, u_int n)
{
	size_t offset;

	if (b->top >= b->len || n > BITMAP_MAX)
		return; /* invalid */
	offset = n / BITMAP_BITS;
	if (offset > b->top)
		return;
	b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
	/* The top may have changed as a result of the clear */
	retop(b);
}

size_t
bitmap_nbits(struct bitmap *b)
{
	size_t bits;
	BITMAP_WTYPE w;

	retop(b);
	if (b->top >= b->len)
		return 0; /* invalid */
	if (b->len == 0 || (b->top == 0 && b->d[0] == 0))
		return 0;
	/* Find MSB set */
	w = b->d[b->top];
	bits = (b->top + 1) * BITMAP_BITS;
	while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
		w <<= 1;
		bits--;
	}
	return bits;
}

size_t
bitmap_nbytes(struct bitmap *b)
{
	return (bitmap_nbits(b) + 7) / 8;
}

int
bitmap_to_string(struct bitmap *b, void *p, size_t l)
{
	u_char *s = (u_char *)p;
	size_t i, j, k, need = bitmap_nbytes(b);

	if (l < need || b->top >= b->len)
		return -1;
	if (l > need)
		l = need;
	/* Put the bytes from LSB backwards */
	for (i = k = 0; i < b->top + 1; i++) {
		for (j = 0; j < BITMAP_BYTES; j++) {
			if (k >= l)
				break;
			s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
		}
	}
	return 0;
}

int
bitmap_from_string(struct bitmap *b, const void *p, size_t l)
{
	int r;
	size_t i, offset, shift;
	const u_char *s = (const u_char *)p;

	if (l > BITMAP_MAX / 8)
		return -1;
	if ((r = reserve(b, l * 8)) != 0)
		return r;
	bitmap_zero(b);
	if (l == 0)
		return 0;
	b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
	shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
	for (i = 0; i < l; i++) {
		b->d[offset] |= (BITMAP_WTYPE)s[i] << shift;
		if (shift == 0) {
			offset--;
			shift = BITMAP_BITS - 8;
		} else
			shift -= 8;
	}
	retop(b);
	return 0;
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
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 <sys/types.h>
19			#include <string.h>
20			#include <stdlib.h>
21
22			#include "bitmap.h"
23
24			#define BITMAP_WTYPE u_int
25			#define BITMAP_MAX (1<<24)
26			#define BITMAP_BYTES (sizeof(BITMAP_WTYPE))
27			#define BITMAP_BITS (sizeof(BITMAP_WTYPE) * 8)
28			#define BITMAP_WMASK ((BITMAP_WTYPE)BITMAP_BITS - 1)
29			struct bitmap {
30			BITMAP_WTYPE *d;
31			size_t len; /* number of words allocated */
32			size_t top; /* index of top word allocated */
33			};
34
35			struct bitmap *
36			bitmap_new(void)
37			{
38			struct bitmap *ret;
39
40			if ((ret = calloc(1, sizeof(*ret))) == NULL)
41			return NULL;
42			if ((ret->d = calloc(1, BITMAP_BYTES)) == NULL) {
43			free(ret);
44			return NULL;
45			}
46			ret->len = 1;
47			ret->top = 0;
48			return ret;
49			}
50
51			void
52			bitmap_free(struct bitmap *b)
53			{
54			if (b != NULL && b->d != NULL) {
55			bitmap_zero(b);
56			free(b->d);
57			b->d = NULL;
58			}
59			free(b);
60			}
61
62			void
63			bitmap_zero(struct bitmap *b)
64			{
65			memset(b->d, 0, b->len * BITMAP_BYTES);
66			b->top = 0;
67			}
68
69			int
70			bitmap_test_bit(struct bitmap *b, u_int n)
71			{
72			if (b->top >= b->len)
73			return 0; /* invalid */
74			if (b->len == 0 \|\| (n / BITMAP_BITS) > b->top)
75			return 0;
76			return (b->d[n / BITMAP_BITS] >> (n & BITMAP_WMASK)) & 1;
77			}
78
79			static int
80			reserve(struct bitmap *b, u_int n)
81			{
82			BITMAP_WTYPE *tmp;
83			size_t nlen;
84
85			if (b->top >= b->len \|\| n > BITMAP_MAX)
86			return -1; /* invalid */
87			nlen = (n / BITMAP_BITS) + 1;
88			if (b->len < nlen) {
89			if ((tmp = recallocarray(b->d, b->len,
90			nlen, BITMAP_BYTES)) == NULL)
91			return -1;
92			b->d = tmp;
93			b->len = nlen;
94			}
95			return 0;
96			}
97
98			int
99			bitmap_set_bit(struct bitmap *b, u_int n)
100			{
101			int r;
102			size_t offset;
103
104			if ((r = reserve(b, n)) != 0)
105			return r;
106			offset = n / BITMAP_BITS;
107			if (offset > b->top)
108			b->top = offset;
109			b->d[offset] \|= (BITMAP_WTYPE)1 << (n & BITMAP_WMASK);
110			return 0;
111			}
112
113			/* Resets b->top to point to the most significant bit set in b->d */
114			static void
115			retop(struct bitmap *b)
116			{
117			if (b->top >= b->len)
118			return;
119			while (b->top > 0 && b->d[b->top] == 0)
120			b->top--;
121			}
122
123			void
124			bitmap_clear_bit(struct bitmap *b, u_int n)
125			{
126			size_t offset;
127
128			if (b->top >= b->len \|\| n > BITMAP_MAX)
129			return; /* invalid */
130			offset = n / BITMAP_BITS;
131			if (offset > b->top)
132			return;
133			b->d[offset] &= ~((BITMAP_WTYPE)1 << (n & BITMAP_WMASK));
134			/* The top may have changed as a result of the clear */
135			retop(b);
136			}
137
138			size_t
139			bitmap_nbits(struct bitmap *b)
140			{
141			size_t bits;
142			BITMAP_WTYPE w;
143
144			retop(b);
145			if (b->top >= b->len)
146			return 0; /* invalid */
147			if (b->len == 0 \|\| (b->top == 0 && b->d[0] == 0))
148			return 0;
149			/* Find MSB set */
150			w = b->d[b->top];
151			bits = (b->top + 1) * BITMAP_BITS;
152			while (!(w & ((BITMAP_WTYPE)1 << (BITMAP_BITS - 1)))) {
153			w <<= 1;
154			bits--;
155			}
156			return bits;
157			}
158
159			size_t
160			bitmap_nbytes(struct bitmap *b)
161			{
162			return (bitmap_nbits(b) + 7) / 8;
163			}
164
165			int
166			bitmap_to_string(struct bitmap b, void p, size_t l)
167			{
168			u_char s = (u_char )p;
169			size_t i, j, k, need = bitmap_nbytes(b);
170
171			if (l < need \|\| b->top >= b->len)
172			return -1;
173			if (l > need)
174			l = need;
175			/* Put the bytes from LSB backwards */
176			for (i = k = 0; i < b->top + 1; i++) {
177			for (j = 0; j < BITMAP_BYTES; j++) {
178			if (k >= l)
179			break;
180			s[need - 1 - k++] = (b->d[i] >> (j * 8)) & 0xff;
181			}
182			}
183			return 0;
184			}
185
186			int
187			bitmap_from_string(struct bitmap b, const void p, size_t l)
188			{
189			int r;
190			size_t i, offset, shift;
191			const u_char s = (const u_char )p;
192
193			if (l > BITMAP_MAX / 8)
194			return -1;
195			if ((r = reserve(b, l * 8)) != 0)
196			return r;
197			bitmap_zero(b);
198			if (l == 0)
199			return 0;
200			b->top = offset = ((l + (BITMAP_BYTES - 1)) / BITMAP_BYTES) - 1;
201			shift = ((l + (BITMAP_BYTES - 1)) % BITMAP_BYTES) * 8;
202			for (i = 0; i < l; i++) {
203			b->d[offset] \|= (BITMAP_WTYPE)s[i] << shift;
204			if (shift == 0) {
205			offset--;
206			shift = BITMAP_BITS - 8;
207			} else
208			shift -= 8;
209			}
210			retop(b);
211			return 0;
212			}