prosody
6cdc6923d65a
spec/util_strbitop_spec.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Annotate

spec/util_strbitop_spec.lua @ 13429:6cdc6923d65a

util.strbitop: Add common_prefix_bits() method This returns the number of bits that two strings have in common. It is significantly more efficient than similar calculations in Lua.
author Matthew Wild <mwild1@gmail.com>
date Fri, 23 Feb 2024 12:08:37 +0000
parent 13427:9677df320992
child 13430:1a5e3cf037f6
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
11168
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
1 local strbitop = require "util.strbitop";
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
2 describe("util.strbitop", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
3 describe("sand()", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
4 it("works", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
5 assert.equal(string.rep("Aa", 100), strbitop.sand(string.rep("a", 200), "Aa"));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
6 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
7 it("returns empty string if first argument is empty", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
8 assert.equal("", strbitop.sand("", ""));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
9 assert.equal("", strbitop.sand("", "key"));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
10 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
11 it("returns initial string if key is empty", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
12 assert.equal("hello", strbitop.sand("hello", ""));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
13 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
14 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
15
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
16 describe("sor()", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
17 it("works", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
18 assert.equal(string.rep("a", 200), strbitop.sor(string.rep("Aa", 100), "a"));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
19 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
20 it("returns empty string if first argument is empty", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
21 assert.equal("", strbitop.sor("", ""));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
22 assert.equal("", strbitop.sor("", "key"));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
23 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
24 it("returns initial string if key is empty", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
25 assert.equal("hello", strbitop.sor("hello", ""));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
26 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
27 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
28
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
29 describe("sxor()", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
30 it("works", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
31 assert.equal(string.rep("Aa", 100), strbitop.sxor(string.rep("a", 200), " \0"));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
32 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
33 it("returns empty string if first argument is empty", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
34 assert.equal("", strbitop.sxor("", ""));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
35 assert.equal("", strbitop.sxor("", "key"));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
36 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
37 it("returns initial string if key is empty", function ()
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
38 assert.equal("hello", strbitop.sxor("hello", ""));
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
39 end);
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
40 end);
13429
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
41
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
42 describe("common_prefix_bits()", function ()
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
43 local function B(s)
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
44 assert(#s%8==0, "Invalid test input: B(s): s should be a multiple of 8 bits in length");
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
45 local byte = 0;
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
46 local out_str = {};
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
47 for i = 1, #s do
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
48 local bit_ascii = s:byte(i);
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
49 if bit_ascii == 49 then -- '1'
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
50 byte = byte + 2^((7-(i-1))%8);
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
51 elseif bit_ascii ~= 48 then
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
52 error("Invalid test input: B(s): s should contain only '0' or '1' characters");
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
53 end
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
54 if (i-1)%8 == 7 then
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
55 table.insert(out_str, string.char(byte));
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
56 byte = 0;
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
57 end
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
58 end
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
59 return table.concat(out_str);
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
60 end
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
61
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
62 local _cpb = strbitop.common_prefix_bits;
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
63 local function test(a, b)
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
64 local Ba, Bb = B(a), B(b);
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
65 local ret1 = _cpb(Ba, Bb);
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
66 local ret2 = _cpb(Bb, Ba);
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
67 assert(ret1 == ret2, ("parameter order should not make a difference to the result (%s, %s) = %d, reversed = %d"):format(a, b, ret1, ret2));
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
68 return ret1;
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
69 end
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
70 local hex = require "util.hex";
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
71 it("works on single bytes", function ()
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
72 assert.equal(0, test("00000000", "11111111"));
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
73 assert.equal(1, test("10000000", "11111111"));
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
74 assert.equal(0, test("01000000", "11111111"));
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
75 assert.equal(0, test("01000000", "11111111"));
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
76 assert.equal(8, test("11111111", "11111111"));
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
77 end);
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
78
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
79 it("works on multiple bytes", function ()
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
80 for i = 0, 16 do
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
81 assert.equal(i, test(string.rep("1", i)..string.rep("0", 16-i), "1111111111111111"));
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
82 end
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
83 end);
6cdc6923d65a util.strbitop: Add common_prefix_bits() method
Matthew Wild <mwild1@gmail.com>
parents: 13427
diff changeset
84 end);
11168
cde600e2fdf9 util.strbitop: Add tests covering basics
Kim Alvefur <zash@zash.se>
parents:
diff changeset
85 end);