Compare two bit vectors past their allocation limits correctly

diff --git a/Util.xs b/Util.xs
index 28fe705bec7846296a88232e785bf2ced3e5b4a2..2c3cc6e8641d0217f0f457a5f6291d870814b78c 100644 (file)
--- a/Util.xs
+++ b/Util.xs
@@ -132,32 +132,56 @@ SV *
 veq(SV *sv1, SV *ss1, SV *sv2, SV *ss2, SV *sl)
 PROTOTYPE: $$$$$
 PREINIT:
- size_t s1, s2, l, o, n;
- char *v1, *v2;
+ size_t s1, s2, l, l1, l2, c1, c2, e1, e2, e;
+ int    res = 1;
+ char  *v1, *v2;
 CODE:
  l = svu_validate_uv(sl, "length");
  if (!l)
   XSRETURN_YES;
  s1 = svu_validate_uv(ss1, "offset");
  s2 = svu_validate_uv(ss2, "offset");
+
  SvUPGRADE(sv1, SVt_PV);
  SvUPGRADE(sv2, SVt_PV);
-
- n  = BV_SIZE(s1 + l);
- o  = SvLEN(sv1);
- if (n > o) {
-  l = o * CHAR_BIT - s1;
+ v1 = SvPVX(sv1);
+ v2 = SvPVX(sv2);
+ c1 = SvCUR(sv1) * CHAR_BIT;
+ c2 = SvCUR(sv2) * CHAR_BIT;
+
+ redo:
+ l1 = s1 + l;
+ l2 = s2 + l;
+ e1 = l1 > c1 ? l1 - c1 : 0;
+ e2 = l2 > c2 ? l2 - c2 : 0;
+ e  = e1 > e2 ? e1 : e2;
+
+ if (l > e) {
+  size_t p = l - e;
+
+  res = bv_eq(v1, s1, v2, s2, p);
+  if (!res || e == 0)
+   goto done;
+
+  /* Bit vectors are equal up to p < l */
+  s1 += p;
+  s2 += p;
+  l   = e;
+  goto redo;
  }
 
- n  = BV_SIZE(s2 + l);
- o  = SvLEN(sv2);
- if (n > o) {
-  l = o * CHAR_BIT - s2;
- }
+ /* l <= max(e1, e2), at least one of the vectors is completely out of bounds */
+ e = e1 < e2 ? e1 : e2;
+ if (l > e) {
+  size_t q = l - e;
 
- v1 = SvPVX(sv1);
- v2 = SvPVX(sv2);
+  if (s1 < c1)
+   res = bv_zero(v1, s1, q);
+  else if (s2 < c2)
+   res = bv_zero(v2, s2, q);
+ }
 
- RETVAL = newSVuv(bv_eq(v1, s1, v2, s2, l));
+ done:
+ RETVAL = newSVuv(res);
 OUTPUT:
  RETVAL

diff --git a/bitvect.h b/bitvect.h
index 0f096fdb7f61ec000de50f0cd8d6705485f5f116..51a7d7893aea84f8bcbc42f58b5074749d3b3861 100644 (file)
--- a/bitvect.h
+++ b/bitvect.h
@@ -332,6 +332,47 @@ INLINE_DECLARE(void bv_move(void *bv_, size_t ts, size_t fs, size_t l))
 #endif /* INLINE_DEFINE */
 #undef T
 
+/* ... Test if zero ........................................................ */
+
+#define T BV_UNIT
+INLINE_DECLARE(int bv_zero(const void *bv_, size_t s, size_t l))
+#ifdef INLINE_DEFINE
+{
+ size_t o;
+ T mask, *bv = (T *) bv_, *end;
+
+ bv += s / BITS(T);
+ o   = s % BITS(T);
+
+ mask = BV_MASK_HIGHER(T, BITS(T) - o);
+ if (o + l <= BITS(T)) {
+  if (o + l < BITS(T))
+   mask &= BV_MASK_LOWER(T, o + l);
+  if (*bv & mask)
+   return 0;
+ } else {
+  if (*bv & mask)
+   return 0;
+  ++bv;
+  l  -= (BITS(T) - o);
+  end = bv + l / BITS(T);
+  for (; bv < end; ++bv) {
+   if (*bv)
+    return 0;
+  }
+  o = l % BITS(T);
+  if (o) {
+   mask = BV_MASK_LOWER(T, o);
+   if (*bv & mask)
+    return 0;
+  }
+ }
+
+ return 1;
+}
+#endif /* INLINE_DEFINE */
+#undef T
+
 /* ... Compare ............................................................. */
 
 #define BV_EQ(T, B1, B2) \