Fix mismoves around the unit size

[perl/modules/Scalar-Vec-Util.git] / bitvect.h

diff --git a/bitvect.h b/bitvect.h
index ab9e01ba6476627df15df8f72271d5633972f751..a90ada96b4a1c5acae52b3f13d9d57519da9c0ca 100644 (file)
--- a/bitvect.h
+++ b/bitvect.h
@@ -21,30 +21,57 @@
 /* 0 <  I <= CHAR_BIT * sizeof(T) */
 #define BV_MASK_HIGHER(T, I) ((~((T) 0)) << (BITS(T) - (I)))
 
-#define BV_DO_ALIGNED(T, A)                \
- mask = BV_MASK_HIGHER(T, BITS(T) - fs);   \
- if (fs + l <= BITS(T)) {                  \
-  /* Branching is apparently useless,      \
-   * but since we can't portably shift     \
-   * CHAR_BITS from a char...              \
-   * Actually, we only copy up to this */  \
-  if (fs + l < BITS(T))                    \
-   mask &= BV_MASK_LOWER(T, fs + l);       \
-  *t = (*t & ~mask) | (*f & mask);         \
- } else {                                  \
-  size_t lo, lk;                           \
-  *t = (*t & ~mask) | (*f & mask);         \
-  ++t;                                     \
-  ++f;                                     \
-  l -= (BITS(T) - ts);                     \
-  lo = l % BITS(T);                        \
-  lk = l / BITS(T);                        \
-  BV_##A##_UNIT_ALIGNED(T, t, f, lk);      \
-  if (lo) {                                \
-   mask = BV_MASK_LOWER(T, lo);            \
-   t[lk] = (t[lk] & ~mask)                 \
-         | (f[lk] & mask);                 \
-  }                                        \
+#define BV_DO_ALIGNED_FORWARD(T, A)       \
+ mask = BV_MASK_HIGHER(T, BITS(T) - fs);  \
+ if (fs + l <= BITS(T)) {                 \
+  /* Branching is apparently useless,     \
+   * but since we can't portably shift    \
+   * CHAR_BITS from a char...             \
+   * Actually, we only copy up to this */ \
+  if (fs + l < BITS(T))                   \
+   mask &= BV_MASK_LOWER(T, fs + l);      \
+  *t = (*t & ~mask) | (*f & mask);        \
+ } else {                                 \
+  size_t lo, lk;                          \
+  *t = (*t & ~mask) | (*f & mask);        \
+  ++t;                                    \
+  ++f;                                    \
+  l -= (BITS(T) - ts);                    \
+  lo = l % BITS(T);                       \
+  lk = l / BITS(T);                       \
+  BV_##A##_UNIT_ALIGNED(T, t, f, lk);     \
+  t += lk;                                \
+  f += lk;                                \
+  if (lo) {                               \
+   mask = BV_MASK_LOWER(T, lo);           \
+   *t = (*t & ~mask) | (*f & mask);       \
+  }                                       \
+ }
+
+#define BV_DO_ALIGNED_BACKWARD(T, A)         \
+ if (fs + l <= BITS(T)) {                    \
+  mask = BV_MASK_HIGHER(T, BITS(T) - fs);    \
+  /* Branching is apparently useless,        \
+   * but since we can't portably shift       \
+   * CHAR_BITS from a char...                \
+   * Actually, we only copy up to this */    \
+  if (fs + l < BITS(T))                      \
+   mask &= BV_MASK_LOWER(T, fs + l);         \
+  *t = (*t & ~mask) | (*f & mask);           \
+ } else {                                    \
+  size_t lo, lk;                             \
+  l -= (BITS(T) - ts);                       \
+  lo = l % BITS(T);                          \
+  lk = l / BITS(T);                          \
+  ++t;                                       \
+  ++f;                                       \
+  if (lo) {                                  \
+   mask = BV_MASK_LOWER(T, lo);              \
+   t[lk] = (t[lk] & ~mask) | (f[lk] & mask); \
+  }                                          \
+  BV_##A##_UNIT_ALIGNED(T, t, f, lk);        \
+  mask = BV_MASK_HIGHER(T, BITS(T) - fs);    \
+  t[-1] = (t[-1] & ~mask) | (f[-1] & mask);  \
  }
 
 #define BV_DO_LEFT_FORWARD(T, A)                        \
@@ -158,11 +185,13 @@
   *t = (*t & ~(mask << step)) | ((*f & mask) << step);        \
  } else {                                                     \
   l  -= (BITS(T) - fs);                                       \
-  ins = ((*f & mask) << step) | (*t & BV_MASK_HIGHER(T, ts)); \
+  ins = ((*f & mask) << step);                                \
+  if (ts)                                                     \
+   ins |= (*t & BV_MASK_HIGHER(T, ts));                       \
   --f;                                                        \
   offset = l % BITS(T);                                       \
-  begin  = f - l / BITS(T) - (offset > step);                 \
-  while (f > begin) {                                         \
+  begin  = f - l / BITS(T) + (offset <= step);                \
+  while (f >= begin) {                                        \
    BV_##A##_UNIT_RIGHT_BACKWARD(T, t, f, step);               \
    --t; --f;                                                  \
   }                                                           \
@@ -211,7 +240,7 @@ INLINE_DECLARE(void bv_copy(void *t_, size_t ts, const void *f_, size_t fs, size
  fs %= BITS(T);
 
  if (ts == fs) {
-  BV_DO_ALIGNED(T, COPY);
+  BV_DO_ALIGNED_FORWARD(T, COPY);
  } else if (ts < fs) {
   BV_DO_RIGHT_FORWARD(T, COPY);
  } else { /* ts > fs */
@@ -266,29 +295,31 @@ INLINE_DECLARE(void bv_move(void *bv_, size_t ts, size_t fs, size_t l))
  T ins, tmp, mask, *bv = (T *) bv_, *t, *f;
  const T *begin, *end;
 
- if (!l)
+ if (!l || ts == fs)
   return;
 
  to = ts % BITS(T);
  fo = fs % BITS(T);
 
- if (to == fo) {
-  t  = bv + ts / BITS(T);
-  ts = to;
-  f  = bv + fs / BITS(T);
-  fs = fo;
-  BV_DO_ALIGNED(T, MOVE);
- } else if (ts < fs) {
+ if (ts < fs) {
   t  = bv + ts / BITS(T);
   ts = to;
   f  = bv + fs / BITS(T);
   fs = fo;
-  if (ts < fs) {
+  if (ts == fs) {
+   BV_DO_ALIGNED_FORWARD(T, MOVE);
+  } else if (ts < fs) {
    BV_DO_RIGHT_FORWARD(T, MOVE);
   } else { /* ts > fs */
    BV_DO_LEFT_FORWARD(T, MOVE);
   }
- } else {  /* ts > fs */
+ } else if (to == fo) {
+  t  = bv + ts / BITS(T);
+  ts = to;
+  f  = bv + fs / BITS(T);
+  fs = fo;
+  BV_DO_ALIGNED_BACKWARD(T, MOVE);
+ } else { /* ts > fs */
   size_t z;
   BV_MOVE_INIT_REVERSE(T, t, ts);
   BV_MOVE_INIT_REVERSE(T, f, fs);