Fix mismoves around the unit size

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);

diff --git a/t/32-vcopy-move.t b/t/32-vcopy-move.t
index 1a4cf3a6cad97e816d78fe0c91352cfd7a17d5df..32d981d679f552c305a8042186ba9aa861418128 100644 (file)
--- a/t/32-vcopy-move.t
+++ b/t/32-vcopy-move.t
@@ -10,7 +10,7 @@ use Scalar::Vec::Util qw/vcopy SVU_SIZE/;
 my $p = SVU_SIZE;
 $p = 8 if $p < 8;
 my $n = 3 * $p;
-my $q = 2;
+my $q = 1;
 
 *myfill = *Scalar::Vec::Util::vfill_pp;
 *myeq   = *Scalar::Vec::Util::veq_pp;
@@ -19,27 +19,50 @@ sub rst { myfill($_[0], 0, $n, 0); $_[0] = '' }
 
 sub pat {
  (undef, my $a, my $b, my $x) = @_;
- $_[0] = '';
- if ($b) {
-  myfill($_[0], 0, $a, $x);
-  myfill($_[0], $a, $b, 1 - $x);
+ unless ($b) {
+  rst $_[0];
+ } else {
+  $_[0] = '';
+  myfill($_[0], 0,       $a,             $x);
+  myfill($_[0], $a,      $b,             1 - $x);
+  myfill($_[0], $a + $b, $n - ($a + $b), $x) if $a + $b < $n;
  }
 }
 
+sub prnt {
+ (undef, my $n, my $desc) = @_;
+ my $i = 0;
+ my $s;
+ $s .= vec($_[0], $i++, 1) while $i < $n;
+ diag "$desc: $s";
+}
+
 my ($v, $c) = ('') x 2;
 
-my @s = ($p - $q) .. ($p + $q);
+my @s = (0 .. $q, ($p - $q) .. ($p + $q));
 for my $s1 (@s) {
  for my $s2 (@s) {
   for my $l (0 .. $n - 1) {
-   last if $s1 + $l > $n or $s2 + $l > $n;
-   pat $v, $s1, $l, 0;
-   $c = '';
-   myfill($c, $s1, $l, 1);
-   myfill($c, $s2, $l, 1);
-   vcopy $v => $s1, $v => $s2, $l;
-   ok(myeq($v, 0, $c, 0, $n), "vcopy $s1, $s2, $l (move)");
-   is(length $v, length $c, "length is ok");
+   for my $x (0 .. $q) {
+    for my $y (0 .. $q) {
+     last if $s1 + $l + $x > $n or $s1 + $x + $y > $l
+          or $s2 + $l + $x > $n or $s2 + $x + $y > $l;
+     pat $v, $s1 + $x, $l - $x - $y, 0;
+     my $v0 = $v;
+     $c = $v;
+     myfill($c, $s2,           $x,           0) if $x;
+     myfill($c, $s2 + $x,      $l - $x - $y, 1);
+     myfill($c, $s2 + $l - $y, $y,           0) if $y;
+     vcopy $v => $s1, $v => $s2, $l;
+     ok(myeq($v, 0, $c, 0, $n), "vcopy [ $x, $y ], $s1, $s2, $l (move)") or do {
+      diag "n = $n, s1 = $s1, s2 = $s2, l = $l, x = $x, y = $y";
+      prnt $v0, $n, 'original';
+      prnt $v,  $n, 'got     ';
+      prnt $c,  $n, 'expected';
+     };
+     is(length $v, length $c, "length is ok");
+    }
+   }
   }
  }
 }