From: Vincent Pit Date: Sun, 17 May 2009 15:03:15 +0000 (+0200) Subject: Fix mismoves around the unit size X-Git-Tag: v0.06~8 X-Git-Url: http://git.vpit.fr/?p=perl%2Fmodules%2FScalar-Vec-Util.git;a=commitdiff_plain;h=c8cc00e5e84cd54ed1a7a9858d8ed029bd6d5931 Fix mismoves around the unit size --- diff --git a/bitvect.h b/bitvect.h index ab9e01b..a90ada9 100644 --- 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 1a4cf3a..32d981d 100644 --- 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"); + } + } } } }