summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2007-10-12 21:42:17 (GMT)
committerH. Peter Anvin <hpa@zytor.com>2007-10-12 21:42:17 (GMT)
commit0cd74bdefb565f90a7f8fe91c377dab5af436bb1 (patch)
tree52fdb979c25ebd565d7297e44d46fe8ba7a857c6
parent58b1c821c143af73888a254ee9aaa70d66e0fd3d (diff)
downloadpbn-0cd74bdefb565f90a7f8fe91c377dab5af436bb1.zip
pbn-0cd74bdefb565f90a7f8fe91c377dab5af436bb1.tar.gz
pbn-0cd74bdefb565f90a7f8fe91c377dab5af436bb1.tar.bz2
pbn-0cd74bdefb565f90a7f8fe91c377dab5af436bb1.tar.xz
Add bitwise operations
Add bitwise operations: and, or, xor, set_bit, clr_bit, bit
-rw-r--r--Makefile3
-rw-r--r--pbn.h34
-rw-r--r--pbn_add.c6
-rw-r--r--pbn_and.c53
-rw-r--r--pbn_bit.c58
-rw-r--r--pbn_cmp.c2
-rw-r--r--pbn_init.c14
-rw-r--r--pbn_mul.c4
-rw-r--r--pbn_or.c52
-rw-r--r--pbn_xor.c50
-rw-r--r--pbnint.h1
11 files changed, 246 insertions, 31 deletions
diff --git a/Makefile b/Makefile
index 3fc5782..e00843b 100644
--- a/Makefile
+++ b/Makefile
@@ -2,7 +2,8 @@ CC = gcc
CFLAGS = -g -D_FORTIFY_SOURCE=2 -W -Wall
LDFLAGS =
-LIBOBJ = pbn_add.o pbn_cmp.o pbn_dump.o pbn_init.o pbn_mul.o pbn_shift.o
+LIBOBJ = pbn_add.o pbn_cmp.o pbn_dump.o pbn_init.o pbn_mul.o pbn_shift.o \
+ pbn_and.o pbn_or.o pbn_xor.o pbn_bit.o
TESTS = test
diff --git a/pbn.h b/pbn.h
index 1dae30b..2ae2f4a 100644
--- a/pbn.h
+++ b/pbn.h
@@ -49,30 +49,40 @@ struct pbn {
#define pbn_ref(x) ((x)->ref++, (x))
-#if defined(__GNUC__) && !defined(PBN_INIT)
-extern inline void pbn_free(struct pbn *__pbn)
-{
- if (! --__pbn->ref)
- _pbn_free(__pbn);
-}
-#else
-void pbn_free(struct pbn *);
-#endif
+#define pbn_free(x) \
+ do { \
+ struct pbn *__pbn = (x); \
+ if (! --__pbn->ref) \
+ _pbn_free(__pbn); \
+ } while (0)
+
struct pbn *pbn_addsub(struct pbn *, struct pbn *, int issub);
#define pbn_add(x,y) pbn_addsub(x,y,0)
#define pbn_sub(x,y) pbn_addsub(x,y,1)
-int pbn_cmp(struct pbn *, struct pbn *);
+/* pbn_cmp() does NOT consume a reference! */
+int pbn_cmp(const struct pbn *, const struct pbn *);
struct pbn *pbn_mul(struct pbn *, struct pbn *);
+
struct pbn *pbn_shr(struct pbn *, int);
struct pbn *pbn_shl(struct pbn *, int);
-void pbn_dump(FILE *, struct pbn *);
+struct pbn *pbn_and(struct pbn *, struct pbn *);
+struct pbn *pbn_or(struct pbn *, struct pbn *);
+struct pbn *pbn_xor(struct pbn *, struct pbn *);
+
+struct pbn *pbn_set_bit(struct pbn *, int);
+struct pbn *pbn_clr_bit(struct pbn *, int);
+/* pbn_bit() does NOT consume a reference! */
+int pbn_bit(const struct pbn *, int);
+
struct pbn *pbn_int(pbn_satom_t);
+
+void pbn_dump(FILE *, struct pbn *);
struct pbn *pbn_new(int);
struct pbn *pbn_dup(const struct pbn *);
struct pbn *pbn_dupx(const struct pbn *, int);
struct pbn *pbn_cow(struct pbn *, int);
/* Internal functions */
-void _pbn_adjust_bits(struct pbn *pbn);
+struct pbn *_pbn_adjust_bits(struct pbn *pbn);
#endif /* PBN_H */
diff --git a/pbn_add.c b/pbn_add.c
index f264b4d..197a282 100644
--- a/pbn_add.c
+++ b/pbn_add.c
@@ -80,7 +80,7 @@ struct pbn *pbn_addsub(struct pbn *s1, struct pbn *s2, int issub)
}
/* Now s1 is the addend and s2 is the subtrahend */
- if (pbn_cmp(s1, s2) < 0) {
+ if (pbn_cmp(pbn_ref(s1), pbn_ref(s2)) < 0) {
/* addend is smaller than subtrahend, reverse and
invert minus */
struct pbn *t = s1;
@@ -120,7 +120,5 @@ struct pbn *pbn_addsub(struct pbn *s1, struct pbn *s2, int issub)
d->minus = dminus;
}
- _pbn_adjust_bits(d);
-
- return d;
+ return _pbn_adjust_bits(d);
}
diff --git a/pbn_and.c b/pbn_and.c
new file mode 100644
index 0000000..e0478e2
--- /dev/null
+++ b/pbn_and.c
@@ -0,0 +1,53 @@
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2007 H. Peter Anvin - All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, Inc.,
+ * 59 Temple Place Ste 330, Boston MA 02111-1307, USA; version 2.1,
+ * incorporated herein by reference.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * pbn_and.c
+ */
+
+#include <string.h>
+#include "pbnint.h"
+
+struct pbn *pbn_and(struct pbn *s1, struct pbn *s2)
+{
+ struct pbn *d;
+ int i, len;
+
+ if (s1->bits == 0) {
+ pbn_free(s1);
+ return s2;
+ } else if (s2->bits == 0) {
+ pbn_free(s2);
+ return s1;
+ }
+
+ if (s1->ref > s2->ref) {
+ struct pbn *t = s1;
+ s1 = s2;
+ s2 = t;
+ }
+
+ d = pbn_cow(s1, s1->len);
+ len = d->len;
+ if (s2->len < len) {
+ len = s2->len;
+ memset(&d->num[len], 0, (d->len-len)*sizeof(pbn_atom_t));
+ }
+
+ for (i = 0; i < d->len; i++)
+ d->num[i] &= s2->num[len];
+
+ pbn_free(s2);
+ return _pbn_adjust_bits(d);
+}
+
+
diff --git a/pbn_bit.c b/pbn_bit.c
new file mode 100644
index 0000000..9049117
--- /dev/null
+++ b/pbn_bit.c
@@ -0,0 +1,58 @@
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2007 H. Peter Anvin - All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, Inc.,
+ * 59 Temple Place Ste 330, Boston MA 02111-1307, USA; version 2.1,
+ * incorporated herein by reference.
+ *
+ * ----------------------------------------------------------------------- */
+
+#include "pbnint.h"
+
+struct pbn *pbn_set_bit(struct pbn *pbn, int bit)
+{
+ int len;
+ pbn_atom_t mask;
+
+ len = (bit+PBN_ATOM_BITS-1)/PBN_ATOM_BITS;
+ if (len < pbn->len)
+ len = pbn->len;
+
+ pbn = pbn_cow(pbn, len);
+ mask = (pbn_atom_t)1 << (bit % PBN_ATOM_BITS);
+ pbn->num[bit/PBN_ATOM_BITS] |= mask;
+
+ bit++;
+ pbn->bits = (bit > pbn->bits) ? bit : pbn->bits;
+
+ return pbn;
+}
+
+struct pbn *pbn_clr_bit(struct pbn *pbn, int bit)
+{
+ pbn_atom_t mask;
+
+ if (bit >= pbn->bits)
+ return pbn;
+
+ pbn = pbn_cow(pbn, pbn->len);
+ mask = (pbn_atom_t)1 << (bit % PBN_ATOM_BITS);
+ pbn->num[bit / PBN_ATOM_BITS] &= ~mask;
+
+ bit++;
+ if (bit == pbn->bits)
+ return _pbn_adjust_bits(pbn); /* We just cleared the MSB */
+ else
+ return pbn;
+}
+
+int pbn_bit(const struct pbn *pbn, int bit)
+{
+ if (bit >= pbn->bits)
+ return 0;
+
+ return (pbn->num[bit/PBN_ATOM_BITS] >> (bit % PBN_ATOM_BITS)) & 1;
+}
diff --git a/pbn_cmp.c b/pbn_cmp.c
index 1a2518d..f67de79 100644
--- a/pbn_cmp.c
+++ b/pbn_cmp.c
@@ -16,7 +16,7 @@
#include "pbnint.h"
-int pbn_cmp(struct pbn *s1, struct pbn *s2)
+int pbn_cmp(const struct pbn *s1, const struct pbn *s2)
{
int lt = s1->minus ? 1 : -1;
int gt = -lt;
diff --git a/pbn_init.c b/pbn_init.c
index a6ce544..c7c053c 100644
--- a/pbn_init.c
+++ b/pbn_init.c
@@ -32,12 +32,6 @@ struct pbn *pbn_new(int len)
return pbn;
}
-void pbn_free(struct pbn *pbn)
-{
- if (! --pbn->ref)
- _pbn_free(pbn);
-}
-
#if PBN_ATOM_BITS != 32 && PBN_ATOM_BITS != 64
# error "Fix pbn_ilog2p1 for new PBN_ATOM_BITS size"
#endif
@@ -148,8 +142,9 @@ struct pbn *pbn_cow(struct pbn *src, int len)
}
/* Adjust the bits field of a specific pbn, and clear the minus flag
- if the value is actually zero. */
-void _pbn_adjust_bits(struct pbn *pbn)
+ if the value is actually zero. Returns its argument, to make
+ tailcalling possible. */
+struct pbn *_pbn_adjust_bits(struct pbn *pbn)
{
int i;
pbn_atom_t v;
@@ -158,10 +153,11 @@ void _pbn_adjust_bits(struct pbn *pbn)
v = pbn->num[i];
if (v) {
pbn->bits = i*PBN_ATOM_BITS + pbn_ilog2p1(v);
- return;
+ return pbn;
}
}
pbn->bits = 0;
pbn->minus = 0;
+ return pbn;
}
diff --git a/pbn_mul.c b/pbn_mul.c
index a85a94f..f7f35f3 100644
--- a/pbn_mul.c
+++ b/pbn_mul.c
@@ -57,8 +57,6 @@ struct pbn *pbn_mul(struct pbn *s1, struct pbn *s2)
pbn_free(s1);
pbn_free(s2);
- _pbn_adjust_bits(d);
-
- return d;
+ return _pbn_adjust_bits(d);
}
diff --git a/pbn_or.c b/pbn_or.c
new file mode 100644
index 0000000..294f401
--- /dev/null
+++ b/pbn_or.c
@@ -0,0 +1,52 @@
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2007 H. Peter Anvin - All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, Inc.,
+ * 59 Temple Place Ste 330, Boston MA 02111-1307, USA; version 2.1,
+ * incorporated herein by reference.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * pbn_or.c
+ */
+
+#include "pbnint.h"
+
+struct pbn *pbn_or(struct pbn *s1, struct pbn *s2)
+{
+ struct pbn *d;
+ int i, len, bits, lx;
+
+ if (s1->bits == 0 && s2->bits == 0) {
+ pbn_free(s2);
+ return s1;
+ }
+
+ if (s1->ref > s2->ref) {
+ struct pbn *t = s1;
+ s1 = s2;
+ s2 = t;
+ }
+
+ len = (s1->len > s2->len) ? s1->len : s2->len;
+ bits = (s1->bits > s2->bits) ? s1->bits : s2->bits;
+
+ if (s1->len < s2->len)
+ len = s2->len;
+
+ d = pbn_cow(s1, len);
+ d->bits = bits; /* Guaranteed accurate */
+ lx = len;
+ if (s2->len < lx)
+ lx = s2->len;
+
+ for (i = 0; i < lx; i++)
+ d->num[i] |= s2->num[len];
+
+ pbn_free(s2);
+ return d;
+}
diff --git a/pbn_xor.c b/pbn_xor.c
new file mode 100644
index 0000000..a104e63
--- /dev/null
+++ b/pbn_xor.c
@@ -0,0 +1,50 @@
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2007 H. Peter Anvin - All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, Inc.,
+ * 59 Temple Place Ste 330, Boston MA 02111-1307, USA; version 2.1,
+ * incorporated herein by reference.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * pbn_xor.c
+ */
+
+#include "pbnint.h"
+
+struct pbn *pbn_xor(struct pbn *s1, struct pbn *s2)
+{
+ struct pbn *d;
+ int i, len, bits, lx;
+
+ if (s1->bits == 0 && s2->bits == 0) {
+ pbn_free(s2);
+ return s1;
+ }
+
+ if (s1->ref > s2->ref) {
+ struct pbn *t = s1;
+ s1 = s2;
+ s2 = t;
+ }
+
+ len = (s1->len > s2->len) ? s1->len : s2->len;
+
+ d = pbn_cow(s1, len);
+ d->bits = bits; /* Guaranteed accurate */
+ lx = len;
+ if (s2->len < lx)
+ lx = s2->len;
+
+ for (i = 0; i < lx; i++)
+ d->num[i] ^= s2->num[len];
+
+ pbn_free(s2);
+ return _pbn_adjust_bits(d);
+}
+
+
diff --git a/pbnint.h b/pbnint.h
index d5a9f1f..8915a1d 100644
--- a/pbnint.h
+++ b/pbnint.h
@@ -19,5 +19,4 @@
#include "pbn.h"
-
#endif /* PBNINT_H */