This is an automated email from the ASF dual-hosted git repository. jihuayu pushed a commit to branch fix-bitop-ci-lint in repository https://gitbox.apache.org/repos/asf/kvrocks.git
commit 776d6ea00afaeb2f96420904110161226c38a60b Author: Nikhil K Tyagi <[email protected]> AuthorDate: Fri May 1 11:02:54 2026 +0530 feat(bitmap): support DIFF, DIFF1, ANDOR, ONE for BITOP command Implements Redis 8.2+ bitwise operations: - DIFF: bits set in X but not in any Y - DIFF1: bits set in any Y but not in X - ANDOR: bits set in X and at least one Y - ONE: bits set in exactly one key Closes #3132 Co-Authored-By: Claude Sonnet 4.6 <[email protected]> --- src/commands/cmd_bit.cc | 8 ++ src/types/redis_bitmap.cc | 68 ++++++--- src/types/redis_bitmap.h | 4 + tests/gocase/unit/type/bitmap/bitmap_test.go | 201 ++++++++++++++++++++++++--- 4 files changed, 248 insertions(+), 33 deletions(-) diff --git a/src/commands/cmd_bit.cc b/src/commands/cmd_bit.cc index ba9f721e9..da97cc6e2 100644 --- a/src/commands/cmd_bit.cc +++ b/src/commands/cmd_bit.cc @@ -219,6 +219,14 @@ class CommandBitOp : public Commander { op_flag_ = kBitOpXor; else if (opname == "not") op_flag_ = kBitOpNot; + else if (opname == "diff") + op_flag_ = kBitOpDiff; + else if (opname == "diff1") + op_flag_ = kBitOpDiff1; + else if (opname == "andor") + op_flag_ = kBitOpAndOr; + else if (opname == "one") + op_flag_ = kBitOpOne; else return {Status::RedisInvalidCmd, errInvalidSyntax}; if (op_flag_ == kBitOpNot && args.size() != 4) { diff --git a/src/types/redis_bitmap.cc b/src/types/redis_bitmap.cc index 8a7cee919..6472abbda 100644 --- a/src/types/redis_bitmap.cc +++ b/src/types/redis_bitmap.cc @@ -548,7 +548,8 @@ rocksdb::Status Bitmap::BitOp(engine::Context &ctx, BitOpFlags op_flag, const st * result in GCC compiling the code using multiple-words load/store * operations that are not supported even in ARM >= v6. */ #ifndef USE_ALIGNED_ACCESS - if (frag_minlen >= sizeof(uint64_t) * 4 && frag_numkeys <= 16) { + if (frag_minlen >= sizeof(uint64_t) * 4 && frag_numkeys <= 16 && + op_flag != kBitOpDiff && op_flag != kBitOpDiff1 && op_flag != kBitOpAndOr && op_flag != kBitOpOne) { auto *lres = reinterpret_cast<uint64_t *>(frag_res.get()); const uint64_t *lp[16]; for (uint64_t i = 0; i < frag_numkeys; i++) { @@ -595,22 +596,55 @@ rocksdb::Status Bitmap::BitOp(engine::Context &ctx, BitOpFlags op_flag, const st uint8_t output = 0, byte = 0; for (; j < frag_maxlen; j++) { - output = (fragments[0].size() <= j) ? 0 : fragments[0][j]; - if (op_flag == kBitOpNot) output = ~output; - for (uint64_t i = 1; i < frag_numkeys; i++) { - byte = (fragments[i].size() <= j) ? 0 : fragments[i][j]; - switch (op_flag) { - case kBitOpAnd: - output &= byte; - break; - case kBitOpOr: - output |= byte; - break; - case kBitOpXor: - output ^= byte; - break; - default: - break; + output = (fragments[0].size() <= j) ? 0 : static_cast<uint8_t>(fragments[0][j]); + if (op_flag == kBitOpNot) { + output = ~output; + } else if (op_flag == kBitOpDiff1) { + // DIFF1: bits set in any Y but not in X (X = fragments[0]) + uint8_t or_rest = 0; + for (uint64_t i = 1; i < frag_numkeys; i++) { + byte = (fragments[i].size() <= j) ? 0 : static_cast<uint8_t>(fragments[i][j]); + or_rest |= byte; + } + output = or_rest & ~output; + } else if (op_flag == kBitOpAndOr) { + // ANDOR: bits set in X AND in at least one Y + uint8_t or_rest = 0; + for (uint64_t i = 1; i < frag_numkeys; i++) { + byte = (fragments[i].size() <= j) ? 0 : static_cast<uint8_t>(fragments[i][j]); + or_rest |= byte; + } + output = output & or_rest; + } else if (op_flag == kBitOpOne) { + // ONE: bits set in exactly one key across all inputs + // xor_acc tracks odd parity, and_acc tracks bits set in 2+ keys + uint8_t xor_acc = output, and_acc = 0; + for (uint64_t i = 1; i < frag_numkeys; i++) { + byte = (fragments[i].size() <= j) ? 0 : static_cast<uint8_t>(fragments[i][j]); + and_acc |= (xor_acc & byte); + xor_acc ^= byte; + } + output = xor_acc & ~and_acc; + } else { + for (uint64_t i = 1; i < frag_numkeys; i++) { + byte = (fragments[i].size() <= j) ? 0 : static_cast<uint8_t>(fragments[i][j]); + switch (op_flag) { + case kBitOpAnd: + output &= byte; + break; + case kBitOpOr: + output |= byte; + break; + case kBitOpXor: + output ^= byte; + break; + case kBitOpDiff: + // DIFF: bits set in X but not in any Y + output &= ~byte; + break; + default: + break; + } } } frag_res[j] = output; diff --git a/src/types/redis_bitmap.h b/src/types/redis_bitmap.h index 32a53cc72..6fa0cc162 100644 --- a/src/types/redis_bitmap.h +++ b/src/types/redis_bitmap.h @@ -34,6 +34,10 @@ enum BitOpFlags { kBitOpOr, kBitOpXor, kBitOpNot, + kBitOpDiff, + kBitOpDiff1, + kBitOpAndOr, + kBitOpOne, }; namespace redis { diff --git a/tests/gocase/unit/type/bitmap/bitmap_test.go b/tests/gocase/unit/type/bitmap/bitmap_test.go index b721b51f2..04c8b9a1e 100644 --- a/tests/gocase/unit/type/bitmap/bitmap_test.go +++ b/tests/gocase/unit/type/bitmap/bitmap_test.go @@ -39,10 +39,14 @@ import ( type BITOP int32 const ( - AND BITOP = 0 - OR BITOP = 1 - XOR BITOP = 2 - NOT BITOP = 3 + AND BITOP = 0 + OR BITOP = 1 + XOR BITOP = 2 + NOT BITOP = 3 + DIFF BITOP = 4 + DIFF1 BITOP = 5 + ANDOR BITOP = 6 + ONE BITOP = 7 ) func Set2SetBit(t *testing.T, rdb *redis.Client, ctx context.Context, key string, bs []byte) { @@ -91,22 +95,69 @@ func SimulateBitOp(op BITOP, values ...[]byte) string { } else { x = '0' } - } - for j := 1; j < len(binaryArray); j++ { - left := int(x - '0') - right := int(binaryArray[j][i] - '0') - switch op { - case AND: - left = left & right - case XOR: - left = left ^ right - case OR: - left = left | right + } else if op == DIFF { + // bits in X but not in any Y + for j := 1; j < len(binaryArray); j++ { + if binaryArray[j][i] == '1' { + x = '0' + } + } + } else if op == DIFF1 { + // bits in any Y but not in X + orRest := byte('0') + for j := 1; j < len(binaryArray); j++ { + if binaryArray[j][i] == '1' { + orRest = '1' + } } - if left == 0 { + if orRest == '1' && x == '0' { + x = '1' + } else { x = '0' + } + } else if op == ANDOR { + // bits in X AND at least one Y + orRest := byte('0') + for j := 1; j < len(binaryArray); j++ { + if binaryArray[j][i] == '1' { + orRest = '1' + } + } + if x == '1' && orRest == '1' { + x = '1' } else { + x = '0' + } + } else if op == ONE { + // bits set in exactly one key + count := 0 + for j := 0; j < len(binaryArray); j++ { + if binaryArray[j][i] == '1' { + count++ + } + } + if count == 1 { x = '1' + } else { + x = '0' + } + } else { + for j := 1; j < len(binaryArray); j++ { + left := int(x - '0') + right := int(binaryArray[j][i] - '0') + switch op { + case AND: + left = left & right + case XOR: + left = left ^ right + case OR: + left = left | right + } + if left == 0 { + x = '0' + } else { + x = '1' + } } } binaryResult = append(binaryResult, x) @@ -413,6 +464,124 @@ func TestBitmap(t *testing.T) { require.EqualValues(t, 32, rdb.BitOpOr(ctx, x, a, b).Val()) }) + t.Run("BITOP DIFF basic", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + // X=0xff, Y=0x0f -> DIFF = 0xf0 (bits in X not in Y) + Set2SetBit(t, rdb, ctx, "x", []byte("\xff")) + Set2SetBit(t, rdb, ctx, "y", []byte("\x0f")) + require.NoError(t, rdb.Do(ctx, "BITOP", "DIFF", "dest", "x", "y").Err()) + require.EqualValues(t, SimulateBitOp(DIFF, []byte("\xff"), []byte("\x0f")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP DIFF with multiple Y keys", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + Set2SetBit(t, rdb, ctx, "x", []byte("\xff")) + Set2SetBit(t, rdb, ctx, "y1", []byte("\x0f")) + Set2SetBit(t, rdb, ctx, "y2", []byte("\xf0")) + require.NoError(t, rdb.Do(ctx, "BITOP", "DIFF", "dest", "x", "y1", "y2").Err()) + require.EqualValues(t, SimulateBitOp(DIFF, []byte("\xff"), []byte("\x0f"), []byte("\xf0")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP DIFF missing key treated as zero", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + Set2SetBit(t, rdb, ctx, "x", []byte("\xaa")) + require.NoError(t, rdb.Do(ctx, "BITOP", "DIFF", "dest", "x", "no-such-key").Err()) + require.EqualValues(t, SimulateBitOp(DIFF, []byte("\xaa"), []byte("\x00")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP DIFF1 basic", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + // X=0xff, Y=0x0f -> DIFF1 = 0x00 (bits in Y not in X, but X has all bits set) + Set2SetBit(t, rdb, ctx, "x", []byte("\xff")) + Set2SetBit(t, rdb, ctx, "y", []byte("\x0f")) + require.NoError(t, rdb.Do(ctx, "BITOP", "DIFF1", "dest", "x", "y").Err()) + require.EqualValues(t, SimulateBitOp(DIFF1, []byte("\xff"), []byte("\x0f")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP DIFF1 with partial overlap", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + // X=0x0f, Y=0xff -> DIFF1 = 0xf0 (bits in Y not in X) + Set2SetBit(t, rdb, ctx, "x", []byte("\x0f")) + Set2SetBit(t, rdb, ctx, "y", []byte("\xff")) + require.NoError(t, rdb.Do(ctx, "BITOP", "DIFF1", "dest", "x", "y").Err()) + require.EqualValues(t, SimulateBitOp(DIFF1, []byte("\x0f"), []byte("\xff")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP ANDOR basic", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + // X=0xff, Y=0x0f -> ANDOR = 0x0f (bits in X AND at least one Y) + Set2SetBit(t, rdb, ctx, "x", []byte("\xff")) + Set2SetBit(t, rdb, ctx, "y", []byte("\x0f")) + require.NoError(t, rdb.Do(ctx, "BITOP", "ANDOR", "dest", "x", "y").Err()) + require.EqualValues(t, SimulateBitOp(ANDOR, []byte("\xff"), []byte("\x0f")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP ANDOR with multiple Y keys", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + Set2SetBit(t, rdb, ctx, "x", []byte("\xff")) + Set2SetBit(t, rdb, ctx, "y1", []byte("\x0f")) + Set2SetBit(t, rdb, ctx, "y2", []byte("\xf0")) + require.NoError(t, rdb.Do(ctx, "BITOP", "ANDOR", "dest", "x", "y1", "y2").Err()) + require.EqualValues(t, SimulateBitOp(ANDOR, []byte("\xff"), []byte("\x0f"), []byte("\xf0")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP ONE basic", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + // A=0xff, B=0x0f -> ONE = 0xf0 (bits set in exactly one key) + Set2SetBit(t, rdb, ctx, "a", []byte("\xff")) + Set2SetBit(t, rdb, ctx, "b", []byte("\x0f")) + require.NoError(t, rdb.Do(ctx, "BITOP", "ONE", "dest", "a", "b").Err()) + require.EqualValues(t, SimulateBitOp(ONE, []byte("\xff"), []byte("\x0f")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP ONE with three keys", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + Set2SetBit(t, rdb, ctx, "a", []byte("\xff")) + Set2SetBit(t, rdb, ctx, "b", []byte("\x0f")) + Set2SetBit(t, rdb, ctx, "c", []byte("\xf0")) + require.NoError(t, rdb.Do(ctx, "BITOP", "ONE", "dest", "a", "b", "c").Err()) + require.EqualValues(t, SimulateBitOp(ONE, []byte("\xff"), []byte("\x0f"), []byte("\xf0")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP ONE single key returns same key", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + Set2SetBit(t, rdb, ctx, "a", []byte("\xaa")) + require.NoError(t, rdb.Do(ctx, "BITOP", "ONE", "dest", "a").Err()) + require.EqualValues(t, SimulateBitOp(ONE, []byte("\xaa")), rdb.Get(ctx, "dest").Val()) + }) + + t.Run("BITOP new ops fuzzing", func(t *testing.T) { + require.NoError(t, rdb.FlushDB(ctx).Err()) + for i := 0; i < 10; i++ { + numKeys := 2 + i%3 + vec := make([][]byte, numKeys) + veckeys := make([]string, numKeys) + for k := 0; k < numKeys; k++ { + vec[k] = []byte(util.RandStringWithSeed(1, 10, util.Binary, int64(i*100+k))) + veckeys[k] = fmt.Sprintf("fuzz-%d-%d", i, k) + Set2SetBit(t, rdb, ctx, veckeys[k], vec[k]) + } + doArgs := func(op string) []interface{} { + args := []interface{}{"BITOP", op, "target"} + for _, k := range veckeys { + args = append(args, k) + } + return args + } + require.NoError(t, rdb.Do(ctx, doArgs("DIFF")...).Err()) + require.EqualValues(t, SimulateBitOp(DIFF, vec...), rdb.Get(ctx, "target").Val()) + + require.NoError(t, rdb.Do(ctx, doArgs("DIFF1")...).Err()) + require.EqualValues(t, SimulateBitOp(DIFF1, vec...), rdb.Get(ctx, "target").Val()) + + require.NoError(t, rdb.Do(ctx, doArgs("ANDOR")...).Err()) + require.EqualValues(t, SimulateBitOp(ANDOR, vec...), rdb.Get(ctx, "target").Val()) + + require.NoError(t, rdb.Do(ctx, doArgs("ONE")...).Err()) + require.EqualValues(t, SimulateBitOp(ONE, vec...), rdb.Get(ctx, "target").Val()) + } + }) + t.Run("BITFIELD and BITFIELD_RO on string type", func(t *testing.T) { t.Parallel() p := util.KeyPrefix(t)
