Bitmask Handling, part 2: Bitmask reconstitution

Posting the first part of my series on bitmasks (yes, this is now officially a series) taught me a lot about my readers: You don’t care about handling bitmasks in the database. And I respect you for that! I’m overjoyed, as a matter of fact! That article has received the least hits of anything I’ve posted in this blog to date. So good for you for not clicking.

However, I’m going to continue and take this thing all the way to the bitter end. Why? I’m not sure, but I think it has something to do with my freshman year computer science course, “Data Structures”. It was a course taught in C++, and the very first project was to create a series of classes that could support working with very large numbers. Of course, this was all handled via a bunch of bit manipulation, but I didn’t know that because slacker that I was, I never went to class and only started the project the night before it was due.

I never finished the project. But out of the kindness of his heart — or madness in his brain — my professor let it slide and I passed the class anyway (I started going to class and completed the rest of the projects after that little slip!)

So here I am with this gaping hole in my education. I never finished the project for large numbers. And I’m really rusty on my C++ at the moment, but I know my way around SQL pretty well.

So what’s next? I’m thinking we’ll start with standard logical operators: AND, OR, NOT. And then move on to right-shift and left-shift. From there, it should be a pretty simple jump to addition, subtraction, multiplication, and division. I think. My other goal — if I can figure out how to do it — is to provide a mechanism by which the user will be able to view a decimal representation (in the form of a string) of the number contained in the bitmask. So this isn’t really “handling bitmasks” anymore — it’s now become “how to represent really big numbers“.

Anyway, on to the meat of this episode (for the 5 people who are probably going to bother reading this)…

We now have a way of taking a bitmask of arbitrary size (up to 4096 bytes, but could be bigger with more rows in the numbers table) and producing a table of integers representing which “bits” are set to 1 in the bitmask. That’s thanks to the splitBitmask function.

Integral to finishing this project is a method of going the other way around — we need to reconstitute bitmasks from a table of integers representing bit positions.

Since this series is a subseries of my series of things not to do in SQL Server, I’m allowed to use all sorts of dirty tricks to accomplish my goal. The trick du jour is aggregate concatenation (don’t you love all of these intra-blog links?). I considered looping and tried to think of a truly set-based solution, but nothing beats the fun of letting SQL Server handle the dirty work in a totally undocumented way.

As you may recall, the BitmaskNumbers table defined in the first article contains three columns: A “Number”, which represents an individual bit, a “Byte”, which represents a collection of 8 bits, and a “BitValue”, which represents the decimal value of that bit within the byte.

Assuming that we have a table of integers representing bit positions, we can join to the BitmaskNumbers table to get the associated bytes and bit values for those bits. So for instance, if we were to split the bitmask 0x1001F3 using the splitBitmask function:

[sql]SELECT
BitmaskNumbers.Number,
BitmaskNumbers.Byte,
BitmaskNumbers.Bitvalue
FROM dbo.splitBitmask(0x1001F3) x
JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number

Number Byte Bitvalue
—— —— ——–
1 1 1
2 1 2
5 1 16
6 1 32
7 1 64
8 1 128
9 2 1
21 3 16
[/sql]

We have three bytes, and the de-aggregated values for the bits in those bytes. Aggregating them is a simple matter of using the SUM() function:

[sql]SELECT
BitmaskNumbers.Byte,
SUM(BitmaskNumbers.Bitvalue) AS TotalValue
FROM dbo.splitBitmask(0x1001F3) x
JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number
GROUP BY BitmaskNumbers.Byte

Byte TotalValue
—— ———–
1 243
2 1
3 16
[/sql]

Of course, that’s a decimal representation and we require hexadecimal…

[sql]SELECT
BitmaskNumbers.Byte,
CONVERT(VARBINARY(1), SUM(BitmaskNumbers.Bitvalue)) AS TotalValue
FROM dbo.splitBitmask(0x1001F3) x
JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number
GROUP BY BitmaskNumbers.Byte
ORDER BY BitmaskNumbers.Byte DESC

Byte TotalValue
—— ———-
3 0x10
2 0x01
1 0xF3
[/sql]

… And now you can see our original three bytes: 0x10, 0x01, and 0xF3. Lucky for those of us who want to do weird things with big bitmasks, SQL Server treats binary values like strings when using the + operator:

[sql]– 0x10 + 0x01 != 17

— Instead:

SELECT 0x10 + 0x01 AS Concat

Concat
——
0x1001
[/sql]

… And one other property that will be useful for aggregate concatenation:

[sql]SELECT 0x00 + 0xFF AS Concat

Concat
——
0x00FF

–That’s not very useful; how do we initialize a NULL varbinary variable to an empty value?

SELECT 0x + 0xFF AS Concat

Concat
——
0xFF

–0x it is…
[/sql]

From here, it’s a simple step to rebuilding the original bitmask:

[sql]DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x

SELECT
@Bitmask = @Bitmask +
CONVERT(VARBINARY(1),
SUM(BitmaskNumbers.Bitvalue)
)
FROM dbo.splitBitmask(0x1001F3) x
JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number
GROUP BY BitmaskNumbers.Byte
ORDER BY BitmaskNumbers.Byte DESC

SELECT @Bitmask AS TheBitmask

TheBitmask
————
0x1001F3
[/sql]

But this bitmask has no blank spots. What if we switch to 0xFF00FF?

[sql]TheBitmask
————
0xFFFF

–That’s not good!
[/sql]

Changing the INNER JOIN to a RIGHT JOIN and adding a NULL check solves the problem a bit:

[sql]DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x

SELECT
@Bitmask = @Bitmask +
CONVERT(VARBINARY(1),
SUM(CASE
WHEN x.Number IS NULL THEN 0
ELSE BitmaskNumbers.BitValue
END)
)
FROM dbo.splitBitmask(0xFF00FF) x
RIGHT JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number
GROUP BY BitmaskNumbers.Byte
ORDER BY BitmaskNumbers.Byte DESC

SELECT @Bitmask AS TheBitmask

TheBitmask
————-
0x00000000000000000000000000000000000000000000 … FF00FF

–Long string of zeroes followed by the original bitmask truncated for brevity
[/sql]

To keep things sparse, we should only take as many bytes as we require. We can filter the results post-join, and also take advantage of the index that was created on the Byte column in the first installment:

[sql]DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x

SELECT
@Bitmask = @Bitmask +
CONVERT(VARBINARY(1),
SUM(CASE
WHEN x.Number IS NULL THEN 0
ELSE BitmaskNumbers.BitValue
END)
)
FROM dbo.splitBitmask(0xFF00FF) x
RIGHT JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number
WHERE BitmaskNumbers.Byte <=
(SELECT
CASE MAX(Number) % 8
WHEN 0 THEN (MAX(Number) – 1) / 8
ELSE MAX(Number) / 8
END + 1
FROM dbo.splitBitmask(0xFF00FF))
GROUP BY BitmaskNumbers.Byte
ORDER BY BitmaskNumbers.Byte DESC

SELECT @Bitmask AS TheBitmask

TheBitmask
————
0xFF00FF

–Finally, the correct re-constituted output
[/sql]

A small optimization is using a table variable for the results of splitBitmask so that it will only have to be executed once. So the final pattern I’ll present for solving this problem, ready for insertion into a variety of new UDFs, is:

[sql]DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x11002200330044

DECLARE @BitsInBitmask TABLE(Number SMALLINT)
INSERT @BitsInBitmask
SELECT Number
FROM dbo.splitBitmask(@Bitmask)

SET @Bitmask = 0x

SELECT @Bitmask = @Bitmask +
CONVERT(VARBINARY(1),
SUM(CASE
WHEN x.Number IS NULL THEN 0
ELSE BitmaskNumbers.BitValue
END)
)
FROM @BitsInBitmask x
RIGHT JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number
WHERE BitmaskNumbers.Byte <=
(SELECT
CASE MAX(Number) % 8
WHEN 0 THEN (MAX(Number) – 1) / 8
ELSE MAX(Number) / 8
END + 1
FROM @BitsInBitmask)
GROUP BY BitmaskNumbers.Byte
ORDER BY BitmaskNumbers.Byte DESC

SELECT @Bitmask AS TheBitmask

TheBitmask
————
0x11002200330044
[/sql]

… And there you have it. Next time I’ll investigate how to use this technique to very easily implement binary logical operators. And perhaps I’ll disclose more tales about my poor study habits. Or maybe not.