Adam Machanic : T-SQL, bitmasks

Bitmask Handling, part 4: Left-shift and right-shift

Adam Machanic — Thu, 13 Jul 2006 01:29:00 GMT

Quick installment this time. Left-shift and right-shift operators.

Left-shift and right-shift are integral to binary mathematical operations as they have two important qualities: Left-shifting a bitmask once multiplies by two. Right-shifting once divides by two. For example:

0011 (base 2) = 1 + 2 = 3

3 << 1 = 0110 (base 2) = 4 + 2 = 6

-- Note that << is the C++ left-shift operator

Or we could go the other way and divide:

0110 (base 2) = 4 + 2 = 6

6 >> 1 = 0011 (base 2) = 2 + 1 = 3


-- But what happens if we do a second right-shift?

3 >> 1 = 0001 (base 2) = 1


-- Now we've lost a bit (it "fell off the edge") -- causing rounding.
-- Luckily, that's the same way SQL Server treats this situation:

SELECT 3 / 2 AS [3_Right_1]


3_Right_1
---------
1

So now you've seen the basics of left-shifting and right-shifting. But how easy is it to implement given the bitmask handling framework already established in previous installments?

Very, very easy!

Remember that 0011 (base 2) is 3 (base 10) or 0x0003 (base 16), and has bits 1 and 2 turned on. Left-shifting once should produce 0110 / 6 / 0x0006 -- bits 2 and 3 turned on.

DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x0003

DECLARE @LeftShiftNum INT
SET @LeftShiftNum = 1


SELECT Number + @LeftShiftNum AS Number
FROM dbo.splitBitmask(@Bitmask)


Number
------
2
3

And that's literally all there is to it. Right-shift is just as easy, but we subtract:

DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x0006

DECLARE @RightShiftNum INT
SET @RightShiftNum = 1


SELECT Number - @RightShiftNum AS Number
FROM dbo.splitBitmask(@Bitmask)


Number
------
1
2

Right-shifting twice will produce an out-of-bounds bit, 0. But that's not an issue, because the bitmask re-constitution pattern uses the bitmaskNumbers table, which conveniently doesn't contain a 0. A bit of accidental foresight on my part, perhaps.

I have nothing more to say on this issue. Plug everything back into the re-constitution pattern and we're done:

CREATE FUNCTION bitwiseLeftShift
(
	@Bitmask VARBINARY(4096),
	@LeftShiftNum INT
)
RETURNS VARBINARY(4096)
AS
BEGIN
	DECLARE @BitsInBitmask TABLE(Number SMALLINT)
	INSERT @BitsInBitmask
	SELECT Number
	FROM
	(
		SELECT Number + @LeftShiftNum AS Number
		FROM dbo.splitBitmask(@Bitmask)
	) x
	
	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

	RETURN(@Bitmask)
END
GO


-- Here are some examples to prove that everything works:


SELECT dbo.bitwiseLeftShift(0x03, 1) AS [3_times_two]
GO


3_times_two
-----------
0x06



SELECT dbo.bitwiseLeftShift(0x03, 3) AS [3_times_eight]
GO


3_times_eight
-------------
0x18



SELECT CONVERT(int, 0x18) AS [int_0x18]


int_0x18
--------
24



SELECT dbo.bitwiseLeftShift(0x18, 12) AS [24_times_4096]


24_times_4096
-------------
0x018000


SELECT CONVERT(int, 0x018000) AS [int_0x018000]


int_0x018000
------------
98304



SELECT 98304 / 4096 AS [this_will_be_24]


this_will_be_24
---------------
24

... and the same for right-shift:

CREATE FUNCTION bitwiseRightShift
(
	@Bitmask VARBINARY(4096),
	@RightShiftNum INT
)
RETURNS VARBINARY(4096)
AS
BEGIN
	DECLARE @BitsInBitmask TABLE(Number SMALLINT)
	INSERT @BitsInBitmask
	SELECT Number
	FROM
	(
		SELECT Number - @RightShiftNum AS Number
		FROM dbo.splitBitmask(@Bitmask)
	) x
	
	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

	RETURN(@Bitmask)
END
GO


--Right-shifting the same number we just left-shifted 12 bits should yeild the same input

SELECT dbo.bitwiseRightShift(0x018000, 12) AS [should_be_0x18]


should_be_0x18
--------------
0x18



--Is overflow handled the same way that SQL Server handles it?

SELECT 
	CONVERT(INT, dbo.bitwiseRightShift(0x018000, 16)) AS [overflow],
	98304 / 65536 AS [98304_divide_65536]

overflow	98304_divide_8192
--------	-----------------
1		1


--Apparently :)

Enough for now. Next installment, the long awaited mathematical operators. Special thanks to Steve Kass for smacking me around a bit in the comments section of the last installment and teaching me how to properly implement signed numbers in a binary system. So the next installment will actually be able to deal with negative integers too. Thanks, Steve!!!

Bitmask Handling, part 3: Logical operators

Adam Machanic — Thu, 13 Jul 2006 01:28:00 GMT

It's been longer than I hoped since my last installment on bitmask / big number handling. Life caught up with me and I've had many thankless tasks to catch up on. But that's over now and I'm back to the general slacking that typifies my days, so welcome to Part 3, handling logical operators.

I'll be discussing four operators in this post. AND, OR, XOR, and NOT. The first three are extremely easy given the framework already built out in the previous two posts. The last one has some problems -- so I'll discuss those first.

I haven't been able to find any mathematical or computer science texts that discuss how to deal with variable-length bitmasks, which is what I'm attempting to define here. Most texts keep the discussion to, at most, two or four bytes, and even then those two or four bytes are stable. But the problem with using a variable number is that it creates some inconsistencies with regards to signing. Take this example:

SELECT 1 AS Oops
WHERE 
	-1 <> 
	CONVERT(INT, CONVERT(VARBINARY, CONVERT(SMALLINT, -1)))


Oops
----
1

So what's happening here? The -1 on the right side of the comparison is being cast into a 2-byte SMALLINT, then converted to VARBINARY (which produces 0xFFFF). Then it's being converted back to INT. But guess what..?

SELECT CONVERT(INT, 0xFFFF) AS Arrgh


Arrgh
-----
65535

So what is SQL Server telling us? That a small -1 is not the same as a bigger -1. -1 <> -1!!!

You're probably asking yourself, "what is this guy talking about, and what does any of this have to do with the topic at hand, implementing a binary NOT operation?" And if that's what you were asking yourself, then good job, because you've asked the correct question. So what do they have to do with each other?

The truth-table for NOT is quite simple:

Input	Result
0	1
1	0

But let's delve a little deeper. The SMALLINT representation of the decimal number 1 in hex is 0x0001. In binary, that's 0000000000000001. If you run that through a logical NOT, the result is 1111111111111110, or 0xFFFE. That's -2. But remember, that's only -2 if you're a SMALLINT. If you're either an INT or a BIGINT, it's 65534. And that's just not consistent. I want to know that any equivalent number into my function yeilds an equivalent number on the way out. So NOT(0x000001) should yeild the same result as NOT(0x000000000001).

... and that result, in the function I provide, will be: 0xFE. One byte in, one byte out. Similar to some prison gang mottos, but that's a topic for a later post.

You'll notice that this is similar to the way I handled the bitmask re-constitution in the last post. So I feel pretty good about this. Sparsity is a good thing.

But this has a very important side-effect. These numbers are now officially and permanently un-signed. We can't deal with sign because we can't know which byte corresponds to the highest byte -- that's variable. And since we can't determine the highest byte, we also can't determine the highest bit in that byte, and so can't know whether or not our number is negative.

But I can live with that. And I hope you can, too. And if you can't, write a solution and send it to me and I'll post it.

So on that note, and without further ado, here's how you figure out which bit positions should be output by a NOT operation:

DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x01

SELECT x.Number 
FROM BitmaskNumbers x
LEFT JOIN dbo.SplitBitmask(@Bitmask) y ON y.Number = x.Number
WHERE y.Number IS NULL
	AND x.Byte <= 
		(SELECT MAX(Byte)
		FROM BitmaskNumbers z
		WHERE z.Number =
			(SELECT MAX(Number)
			FROM dbo.SplitBitmask(@Bitmask)))


Number
-------
2
3
4
5
6
7
8

Pretty simple, really: Split the bitmask and take any numbers within the same byte range that aren't in the bitmask. To reconstitute it, simply modify the reconstitution pattern a bit, stuff it all into a function, and you get:

CREATE FUNCTION bitwiseNot
(
	@Bitmask VARBINARY(4096)
)
RETURNS VARBINARY(4096)
AS
BEGIN
	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 NOT 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

	RETURN(@Bitmask)
END
GO


SELECT dbo.BitwiseNot(0x01) AS Not01


Not01
-----
0xFE

And of course, given the properties I described above:

SELECT dbo.BitwiseNot(0x0000000001) AS Not0000000001


Not0000000001
-------------
0xFE

And now on to the other three logical operations, which are much simpler...

The easiest is OR, which has the following truth table:

+	0	1
0	0	1
1	1	1

And what is that similar to, in relational parlance..? A UNION, perhaps?

SELECT Number
FROM
(
	SELECT Number
	FROM dbo.splitBitmask(0x01)

	UNION

	SELECT Number
	FROM dbo.splitBitmask(0x03)
) x

... and how about exclusive OR (XOR)?

+	0	1
0	0	1
1	1	0

Similar to the UNION, but we only want intersections with exactly one bitmask position... Luckily, SQL is equipped for that:

SELECT Number
FROM
(
	SELECT Number FROM dbo.SplitBitmask(0x01)

	UNION ALL

	SELECT Number FROM dbo.SplitBitmask(0x02)
) x
GROUP BY Number
HAVING COUNT(*) = 1

Finally, the AND operation:

+	0	1
0	0	0
1	0	1

Just like XOR, but you need exactly two bit positions in each intersection:

SELECT Number
FROM
(
	SELECT Number FROM dbo.SplitBitmask(0x01)

	UNION ALL

	SELECT Number FROM dbo.SplitBitmask(0x02)
) x
GROUP BY Number
HAVING COUNT(*) = 2

Putting it all together, I present the following OR, XOR, and AND UDFs:

CREATE FUNCTION bitwiseOr
(
	@Bitmask1 VARBINARY(4096),
	@Bitmask2 VARBINARY(4096)
)
RETURNS VARBINARY(4096)
AS
BEGIN
	DECLARE @BitsInBitmask TABLE(Number SMALLINT)
	INSERT @BitsInBitmask
	SELECT Number
	FROM
	(
		SELECT Number
		FROM dbo.splitBitmask(@Bitmask1)

		UNION

		SELECT Number
		FROM dbo.splitBitmask(@Bitmask2)
	) x
	
	SET @Bitmask1 = 0x
	
	SELECT @Bitmask1 = @Bitmask1 +
		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

	RETURN(@Bitmask1)
END


SELECT dbo.bitwiseOr(0x01, 0x03) AS Or_01_03


Or_01_03
--------
0x03

XOR

CREATE FUNCTION bitwiseXOr
(
	@Bitmask1 VARBINARY(4096),
	@Bitmask2 VARBINARY(4096)
)
RETURNS VARBINARY(4096)
AS
BEGIN
	DECLARE @BitsInBitmask TABLE(Number SMALLINT)
	INSERT @BitsInBitmask
	SELECT Number
	FROM
	(
		SELECT Number
		FROM dbo.splitBitmask(@Bitmask1)

		UNION ALL

		SELECT Number
		FROM dbo.splitBitmask(@Bitmask2)
	) x
	GROUP BY Number
	HAVING COUNT(*) = 1
	
	SET @Bitmask1 = 0x
	
	SELECT @Bitmask1 = @Bitmask1 +
		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

	RETURN(@Bitmask1)
END


SELECT dbo.bitwiseXOr(0x01, 0x03) AS XOr_01_03


XOr_01_03
--------
0x02

... And finally, AND

CREATE FUNCTION bitwiseAnd
(
	@Bitmask1 VARBINARY(4096),
	@Bitmask2 VARBINARY(4096)
)
RETURNS VARBINARY(4096)
AS
BEGIN
	DECLARE @BitsInBitmask TABLE(Number SMALLINT)
	INSERT @BitsInBitmask
	SELECT Number
	FROM
	(
		SELECT Number
		FROM dbo.splitBitmask(@Bitmask1)

		UNION ALL

		SELECT Number
		FROM dbo.splitBitmask(@Bitmask2)
	) x
	GROUP BY Number
	HAVING COUNT(*) = 2
	
	SET @Bitmask1 = 0x
	
	SELECT @Bitmask1 = @Bitmask1 +
		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

	RETURN(@Bitmask1)
END


SELECT dbo.bitwiseAnd(0x01, 0x03) AS And_01_03


And_01_03
--------
0x01

... And that's enough for today's installment. Enjoy..!

Bitmask Handling, part 2: Bitmask reconstitution

Adam Machanic — Thu, 13 Jul 2006 01:27:00 GMT

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:

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

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:

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

Of course, that's a decimal representation and we require hexadecimal...

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

... 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:

-- 0x10 + 0x01 != 17

-- Instead:

SELECT 0x10 + 0x01 AS Concat


Concat 
------ 
0x1001

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

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...

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

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

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

TheBitmask
------------
0xFFFF

--That's not good!

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

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

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:

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

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:

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

... 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.

Correction on bitmask handling

Adam Machanic — Thu, 13 Jul 2006 01:26:00 GMT

In the article on handling bitmasks I posted the other day, I made a fatal error in the splitBitmask function. The function treated the low byte as the first byte, instead of the high byte. Therefore:

0x01 != 0x0001

... and that is not good!

So here's a corrected version that fixes the problem:

CREATE FUNCTION dbo.splitBitmask
(
	@Bitmask VARBINARY(4096)
)
RETURNS TABLE
AS
RETURN
(
	SELECT Number
	FROM BitmaskNumbers
	WHERE (SUBSTRING(@Bitmask, DATALENGTH(@Bitmask) - Byte + 1, 1) & BitValue) = BitValue
		AND Byte <= DATALENGTH(@Bitmask)
)
GO

More to come soon... Bit shifting, logical operators, and other fun ways to annoy this guy:

Dealing with very large bitmasks

Adam Machanic — Thu, 13 Jul 2006 01:25:00 GMT

Continuing in my series of things you should probably not do in SQL Server but sometimes have to, I'm going to do a few posts on dealing with very large bitmasks.

Let me first state my utter hatered of bitmasks in databases. I think they're annoying, make the system difficult to understand, and whether or not they violate the First Normal Form (that's up for discussion), using them is just a sign of bad design.

But as I've said in other posts, I realize that short deadlines and tiny budgets are an issue at most shops, and sometimes we just need to shoehorn in a solution real quick (yeah, as if it's not going to last for the next 5+ years?)

In one case in the past, bitmasks were a very convenient solution to a problem I faced with an access control system. But alas, I only had 8 bytes available to me. Only enough for 64 values. And so that solution failed. And the company failed. And many, many tears were shed... If only I'd been able to figure out how to manipulate a bigger bitmask, I might have saved the little children...

I won't go into any more detail on that particular issue since there are still a few pending lawsuits, but suffice it to say that if that situation were happening today, I probably wouldn't use a bitmask anyway. But you might need one -- so here's how you do it:

First we're going to modify the table of numbers that I'm always telling you that you absolutely must have in every single database.

SELECT (a.number * 256 + b.number) AS Number,
	CASE (a.number * 256 + b.number) % 8 
		WHEN 0 THEN ((a.number * 256 + b.number) - 1) / 8
		ELSE (a.number * 256 + b.number) / 8 
		END + 1 AS Byte,
	POWER(2, CASE (a.number * 256 + b.number) % 8 
		WHEN 0 THEN 8
		ELSE (a.number * 256 + b.number) % 8 
		END-1) AS BitValue
INTO BitmaskNumbers
FROM
	(
		SELECT number
		FROM master..spt_values
		WHERE 
			type = 'P'
			AND number <= 255
	) a (Number),
	(
		SELECT number
		FROM master..spt_values
		WHERE 
			type = 'P'
			AND number <= 255
	) b (Number)
WHERE 
	(a.number * 256 + b.number) BETWEEN 1 AND 32767
GO

CREATE CLUSTERED INDEX IX_Byte ON BitmaskNumbers (Byte)
GO

This will produce a table with 32767 rows. Each row has a Number, which will represent a bit position in our bitmask, a Byte, which will help to parse the bitmask, and a BitValue, which is the value that the individual bits within each byte represent. Feel my 1960-esque skill!

The brighter bulbs in my audience have now figured out that I'm going to show you how to handle a 4096-byte bitmask -- capable of handling up to 32767 values. Not bad. But if you need more, just put more rows in the BitmaskNumbers table.

So what do you want to do with bitmasks? Most of the queries I've seen involve access control And for those queries, you want to use a logical and and see if it evaluates to a number other than 0. That is, we want to see if both bitmasks we're comparing have any of the same bits set.

Using what little math knowledge I have managed to retain, I conjured up the following, which indicates which bit positions, based on the "number", are filled in a bitmask. For instance:

DECLARE@x VARBINARY(4096)
SET @Bitmask = 0x1F0000000000000000000000000000000000000000000000000000000000000000000000123000000000000000000000000001

SELECT Number
FROM BitmaskNumbers
WHERE (SUBSTRING(@Bitmask, Byte, 1) & BitValue) = BitValue
	AND Byte <= DATALENGTH(@Bitmask)


Number
----------
1
2
3
4
5
290
293
301
302
401

Fun stuff, no?

The Byte <= DATALENGTH(@x) allows SQL Server to utilize the clustered index on Byte, so that a full table scan doesn't have to happen every single time. Small optimization. I couldn't think of any others. If you can, drop me a line...

Those of you who've read this far are probably yawning and wondering where the access control stuff is... Who cares about chunking up the bitmask into its bit positions? Well, it's simply the first step. Bear with me.

What we need to do is wrap this in a UDF. Then if we had two bitmasks, we could join the bit positions to eliminate those that aren't in common...

CREATE FUNCTION dbo.splitBitmask
(
	@Bitmask VARBINARY(4096)
)
RETURNS TABLE
AS
RETURN
(
	SELECT Number
	FROM BitmaskNumbers
	WHERE (SUBSTRING(@Bitmask, Byte, 1) & BitValue) = BitValue
		AND Byte <= DATALENGTH(@Bitmask)
)
GO

DECLARE @Bitmask1 VARBINARY(4096)
SET @Bitmask1 = 0x1F0000000000000000000000000000000000000000000000000000000000000000000000123000000000000000000000000001

DECLARE @Bitmask2 VARBINARY(4096)
SET @Bitmask2 = 0x0E0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

SELECT x.Number
FROM dbo.splitBitmask(@Bitmask1) x
JOIN dbo.splitBitmask(@Bitmask2) y ON x.Number = y.Number
GO


Number
----------
2
3
4

We now know that these two bitmasks share bits 2, 3, and 4 in common. But for most access control situations, we don't care what bits they share in common -- just that they share some.

CREATE FUNCTION dbo.HasAccess
(
	@Bitmask1 VARBINARY(4096),
	@Bitmask2 VARBINARY(4096)
)
RETURNS BIT
AS
BEGIN
	DECLARE @Result BIT

	SELECT @Result = 
		CASE COUNT(*)
			WHEN 0 THEN 0
			ELSE 1
		END
	FROM dbo.splitBitmask(@Bitmask1) x
	JOIN dbo.splitBitmask(@Bitmask2) y ON x.Number = y.Number

	RETURN (@Result)
END
GO

DECLARE @Bitmask1 VARBINARY(4096)
SET @Bitmask1 = 0x1F0000000000000000000000000000000000000000000000000000000000000000000000123000000000000000000000000001

DECLARE @Bitmask2 VARBINARY(4096)
SET @Bitmask2 = 0x0E0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

SELECT dbo.HasAccess(@Bitmask1, @Bitmask2) AS HasAccess
GO


HasAccess
-------------
1

... And that is pretty much it for this installment. We can now determine whether or not two bitmasks have bits in common, and if necessary which bits they share.

Future installments will cover how to manipulate large bitmasks in other ways -- flip specific bits, perform a logical and that produces a bitmask instead of a result set, and perform a logical or that produces a bitmask. All very useful stuff if you need to work with these bitmasks. But now I just need to figure out how to do all of that stuff.

So until next time.... Don't use this technique.