bitstring.c revision 290001 
1/*
2 * Copyright (C) 2004, 2005, 2007  Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2001  Internet Software Consortium.
4 *
5 * Permission to use, copy, modify, and/or 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 ISC DISCLAIMS ALL WARRANTIES WITH
10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15 * PERFORMANCE OF THIS SOFTWARE.
16 */
17
18/* $Id: bitstring.c,v 1.17 2007/06/19 23:47:17 tbox Exp $ */
19
20/*! \file */
21
22#include <config.h>
23
24#include <stddef.h>
25
26#include <isc/magic.h>
27#include <isc/bitstring.h>
28#include <isc/util.h>
29
30#define DIV8(x)			((x) >> 3)
31#define MOD8(x)			((x) & 0x00000007U)
32#define OCTETS(n)		(((n) + 7) >> 3)
33#define PADDED(n)		((((n) + 7) >> 3) << 3)
34#define BITSET(bs, n) 		(((bs)->data[DIV8(n)] & \
35				 (1 << (7 - MOD8(n)))) != 0)
36#define SETBIT(bs, n)		(bs)->data[DIV8(n)] |= (1 << (7 - MOD8(n)))
37#define CLEARBIT(bs, n)		(bs)->data[DIV8(n)] &= ~(1 << (7 - MOD8(n)))
38
39#define BITSTRING_MAGIC		ISC_MAGIC('B', 'S', 't', 'r')
40#define VALID_BITSTRING(b)	ISC_MAGIC_VALID(b, BITSTRING_MAGIC)
41
42void
43isc_bitstring_init(isc_bitstring_t *bitstring, unsigned char *data,
44		   unsigned int length, unsigned int size, isc_boolean_t lsb0)
45{
46	/*
47	 * Make 'bitstring' refer to the bitstring of 'size' bits starting
48	 * at 'data'.  'length' bits of the bitstring are valid.  If 'lsb0'
49	 * is set then, bit 0 refers to the least significant bit of the
50	 * bitstring.  Otherwise bit 0 is the most significant bit.
51	 */
52
53	REQUIRE(bitstring != NULL);
54	REQUIRE(data != NULL);
55	REQUIRE(length <= size);
56
57	bitstring->magic = BITSTRING_MAGIC;
58	bitstring->data = data;
59	bitstring->length = length;
60	bitstring->size = size;
61	bitstring->lsb0 = lsb0;
62}
63
64void
65isc_bitstring_invalidate(isc_bitstring_t *bitstring) {
66
67	/*
68	 * Invalidate 'bitstring'.
69	 */
70
71	REQUIRE(VALID_BITSTRING(bitstring));
72
73	bitstring->magic = 0;
74	bitstring->data = NULL;
75	bitstring->length = 0;
76	bitstring->size = 0;
77	bitstring->lsb0 = ISC_FALSE;
78}
79
80void
81isc_bitstring_copy(isc_bitstring_t *source, unsigned int sbitpos,
82		   isc_bitstring_t *target, unsigned int tbitpos,
83		   unsigned int n)
84{
85	unsigned int tlast;
86
87	/*
88	 * Starting at bit 'sbitpos', copy 'n' bits from 'source' to
89	 * the 'n' bits of 'target' starting at 'tbitpos'.
90	 */
91
92	REQUIRE(VALID_BITSTRING(source));
93	REQUIRE(VALID_BITSTRING(target));
94	REQUIRE(source->lsb0 == target->lsb0);
95	if (source->lsb0) {
96		REQUIRE(sbitpos <= source->length);
97		sbitpos = PADDED(source->size) - sbitpos;
98		REQUIRE(sbitpos >= n);
99		sbitpos -= n;
100	} else
101		REQUIRE(sbitpos + n <= source->length);
102	tlast = tbitpos + n;
103	if (target->lsb0) {
104		REQUIRE(tbitpos <= target->length);
105		tbitpos = PADDED(target->size) - tbitpos;
106		REQUIRE(tbitpos >= n);
107		tbitpos -= n;
108	} else
109		REQUIRE(tlast <= target->size);
110
111	if (tlast > target->length)
112		target->length = tlast;
113
114	/*
115	 * This is far from optimal...
116	 */
117
118	while (n > 0) {
119		if (BITSET(source, sbitpos))
120			SETBIT(target, tbitpos);
121		else
122			CLEARBIT(target, tbitpos);
123		sbitpos++;
124		tbitpos++;
125		n--;
126	}
127}
128