Link to home
Start Free TrialLog in
Avatar of pbringetto
pbringetto

asked on

bitwise operation on VARBINARY data type(up to 8000 bytes)

trying to figure out a way to pass a delimited string of numeric values to a stored procedure that performs bitwise operation on VARBINARY data type(up to 8000 bytes) and returns rows with matching bit positions.

prc_select ‘1’ would return
all rows in binary column w/
0x0000000000000000000000000000000000000000000000000000000000000001
0x0000000000000000000000000000000000000000000080000000000000000001
0x0000000000000000030000000000000000000000000000000000000000000001

prc_select ‘1,32’ would return
all rows in binary column w/
0x0000000000000000000000040000000000000000000000000000000080000001
0x0000000000000000800000000000000000000000000000000000000000000001
0x0000000000000000000000040000000000000000000000000000000080000000

prc_select ‘255’ would return
all rows in binary column w/
0x4000000000000003000000000000010000000000000000000000000000000003
0x4000000000000000000000084000010000000000300000000000000000000001
Avatar of pbringetto
pbringetto

ASKER

this is what i have so far. it's limited to 16 byte values. needs to work on values of varied length...

CREATE PROCEDURE prc_selectRecordMaster(@string VARCHAR(4000)) AS
--pass offertype and delimited string of style IDs
--prc_select_auction_mstr 2,'1-3-45'
DECLARE @bitmask BINARY(16)
DECLARE @bitmask_group1 BINARY(4) DECLARE @bitmask_group2
BINARY(4) DECLARE @bitmask_group3 BINARY(4) DECLARE @bitmask_group4 BINARY(4)
SET @bitmask_group1=0x00000000 SET @bitmask_group2=0x00000000
SET @bitmask_group3=0x00000000 SET @bitmask_group4=0x00000000
DECLARE @bitposition INT
CREATE TABLE #bitpositions (value INT)
INSERT #bitpositions EXEC prc_parseDelimitedString @string DECLARE bitposition_cursor CURSOR FOR
SELECT value FROM #bitpositions
OPEN bitposition_cursor
FETCH NEXT FROM bitposition_cursor INTO @bitposition
WHILE @@FETCH_STATUS=0
BEGIN
IF @bitposition>96
BEGIN
IF @bitposition=128
BEGIN
SET @bitposition=@bitposition-97
SET @bitmask_group4=@bitmask_group4|CAST(0x80000000 AS INT)
SET @bitmask_group1=@bitmask_group1|CAST(@bitmask_group1 AS INT)
SET @bitmask_group3=@bitmask_group3|CAST(@bitmask_group3 AS INT)
SET @bitmask_group2=@bitmask_group2|CAST(@bitmask_group2 AS INT)
END
ELSE
BEGIN
SET @bitposition=@bitposition-97
SET @bitmask_group4=@bitmask_group4|POWER(2,@bitposition)
SET @bitmask_group1=@bitmask_group1|CAST(@bitmask_group1 AS INT)
SET @bitmask_group3=@bitmask_group3|CAST(@bitmask_group3 AS INT)
SET @bitmask_group2=@bitmask_group2|CAST(@bitmask_group2 AS INT)
END
END
ELSE IF @bitposition>64
BEGIN
IF @bitposition=96
BEGIN
SET @bitposition=@bitposition-65
SET @bitmask_group3=@bitmask_group3|CAST(0x80000000 AS INT)
SET @bitmask_group1=@bitmask_group1|CAST(@bitmask_group1 AS INT)
SET @bitmask_group4=@bitmask_group4|CAST(@bitmask_group4 AS INT)
SET @bitmask_group2=@bitmask_group2|CAST(@bitmask_group2 AS INT)
END
ELSE
BEGIN
SET @bitposition=@bitposition-65
SET @bitmask_group3=@bitmask_group3|POWER(2,@bitposition)
SET @bitmask_group1=@bitmask_group1|CAST(@bitmask_group1 AS INT)
SET @bitmask_group4=@bitmask_group4|CAST(@bitmask_group4 AS INT)
SET @bitmask_group2=@bitmask_group2|CAST(@bitmask_group2 AS INT)
END
END
ELSE IF @bitposition>32
BEGIN
IF @bitposition=64
BEGIN
SET @bitposition=@bitposition-33
SET @bitmask_group2=@bitmask_group2|CAST(0x80000000 AS INT)
SET @bitmask_group4=@bitmask_group4|CAST(@bitmask_group4 AS INT)
SET @bitmask_group3=@bitmask_group3|CAST(@bitmask_group3 AS INT)
SET @bitmask_group1=@bitmask_group1|CAST(@bitmask_group1 AS INT)
END
ELSE
BEGIN
SET @bitposition=@bitposition-33
SET @bitmask_group2=@bitmask_group2|POWER(2,@bitposition)
SET @bitmask_group1=@bitmask_group1|CAST(@bitmask_group1 AS INT)
SET @bitmask_group3=@bitmask_group3|CAST(@bitmask_group3 AS INT)
SET @bitmask_group4=@bitmask_group4|CAST(@bitmask_group4 AS INT)
END
END
ELSE
BEGIN
IF @bitposition=32
BEGIN
SET @bitmask_group1=@bitmask_group1|CAST(0x80000000 AS INT)
SET @bitmask_group4=@bitmask_group4|CAST(@bitmask_group4 AS INT)
SET @bitmask_group3=@bitmask_group3|CAST(@bitmask_group3 AS INT)
SET @bitmask_group2=@bitmask_group2|CAST(@bitmask_group2 AS INT)
END
ELSE
BEGIN
SET @bitmask_group1=@bitmask_group1|POWER(2,@bitposition-1)
SET @bitmask_group4=@bitmask_group4|CAST(@bitmask_group4 AS INT)
SET @bitmask_group3=@bitmask_group3|CAST(@bitmask_group3 AS INT)
SET @bitmask_group2=@bitmask_group2|CAST(@bitmask_group2 AS INT)
END
END
FETCH NEXT FROM bitposition_cursor INTO @bitposition

END
CLOSE bitposition_cursor DEALLOCATE bitposition_cursor DROP TABLE #bitpositions
SET @bitmask=@bitmask_group4+@bitmask_group3+@bitmask_group2+@bitmask_group1
SELECT * FROM tab_recordMaster WHERE
SUBSTRING(recordMasterAttribute,13,4) = SUBSTRING(recordMasterAttribute,13,4)|CAST(SUBSTRING(@bitmask,13,4) AS INT)
AND SUBSTRING(recordMasterAttribute,9,4) = SUBSTRING(recordMasterAttribute,9,4)|CAST(SUBSTRING(@bitmask,9,4) AS INT)
AND SUBSTRING(recordMasterAttribute,5,4) = SUBSTRING(recordMasterAttribute,5,4)|CAST(SUBSTRING(@bitmask,5,4) AS INT)
AND SUBSTRING(recordMasterAttribute,0,4) = SUBSTRING(recordMasterAttribute,0,4)|CAST(SUBSTRING(@bitmask,0,4) AS INT)
Maybe I'm a bit thick, but can you tell me why

prc_select ‘1’

yields the three binary rows following:

0x0000000000000000000000000000000000000000000000000000000000000001
0x0000000000000000000000000000000000000000000080000000000000000001
0x0000000000000000030000000000000000000000000000000000000000000001

I just don't get it. Maybe if I can understand where you're trying to get to from '1', I would be better able to help.
the '1' or '1,2' represents bit positions of a binary value stored in a varbinary column; the sproc should return all rows with specified 'bit positions' in the 'on' state.

The sproc above performs an OR operation between each integer value (bit position) in the delimited string and the binary value in each row, then returns matches as recordset.

Problem is that it’s limited to 16 bytes; the value in the db is varbinary and varies up to 8000 bytes.

prc_select ‘1’
if bit position 1 is 'on' ...all rows w/ 0x0001 in the varbinary column are returned.
prc_select ‘2’
if bit position 2 is 'on' ...all rows w/ 0x0002              "
prc_select ‘1,2’
if bit position 1,2 is 'on' ...all rows w/ 0x0003           "


Avatar of DanRollins
It looks like you need to break the data into accessible chunks (say, bytes) and then use binary operations on them.

The SUBSTRING function can obtain any one-byte value from a varbinary field:
     http://msdn.microsoft.com/library/default.asp?url=/library/en-us/tsqlref/ts_ca-co_2f3o.asp

------------------------------------------------- set up the test
CREATE TABLE MyTable (
   nIdx      integer,
   yBinData  varbinary(8000)
);
INSERT INTO MyTable (nIdx,yBinData)
VALUES (1,0x112233445566778899AABBCCDDEEFF0011)
----------------------------------------------- end setup

Now,  you can use
  SELECT SUBSTRING( yBinData, 1,1) FROM MyTable WHERE nIdx=1 -- yeilds 0x11
  SELECT SUBSTRING( yBinData, 2,1) FROM MyTable WHERE nIdx=1 -- yeilds 0x22
...
  SELECT SUBSTRING( yBinData, 17,1) FROM MyTable WHERE nIdx=1 -- yeilds 0x11

That is, the binary (1-byte) value of the leftmost two hex digits in the varbinary is returned when the 'start' value is 1, the next two when the 'start' value is 2, and you can select any two digits that way.

Now, to check an arbitrary bit, you need to learn which byte it is in, then create a mask based upon that bit position.

----------------------------------------------- start of testing code

DECLARE @nByteNum       integer
DECLARE @nBitNumInByte integer
DECLARE @nMask            integer
DECLARE @nByteToCheck integer

DECLARE @nBigBitNum     integer  -- the input parm to the sp (1 to 64,000)

DELETE FROM MyTable WHERE nIdx=1
INSERT INTO MyTable (nIdx,yBinData)
VALUES (1,0x010273F405FFFFFFFFFF)  -- edit this and rerun to test

SET @nBigBitNum= 17
SET @nByteNum= @nBigBitNum/8
SET @nBitNumInByte= @nBigBitNum % 8      -- 0,1...6,7
SET @nMask = POWER(2, 8-@nBitNumInByte ) -- 128,64,... 2,1

SET @nByteNum= @nByteNum +1 -- index into varbinary starts at 1 (not 0!!)

SET @nByteToCheck=
       (SELECT SUBSTRING( yBinData, @nByteNum,1)
        FROM MyTable WHERE nIdx=1)

if (@nByteToCheck & @nMask) = @nMask
  BEGIN
     PRINT 'bit ' + CAST(@nBigBitNum AS varchar) + ' is SET (1)'
  END
ELSE
  BEGIN
     PRINT 'bit ' + CAST(@nBigBitNum AS varchar) + ' is CLEAR (0)'
  END

-- Dan
Thanks,

I already have a sproc that turns the 'bit positions' into a binary value. The part I’m having trouble figuring out is how to put it into a where clause and return a resultset.

The binary value will vary so I’m assuming it would require some sort of a loop that splits the binary value into segments and builds the where clause dynamically.

OR a function that can be can placed in the where clause:

SELECT * FROM table WHERE dbo.checkBinaryValue(binaryColumn, value 2 check against) = 1

if match return 1 if not return 0

Given what I said above, once you have calculated the desired byte offset and the correct mask, it looks rather straightforward:

SELECT * FROM MyTable WHERE
       (SUBSTRING( yBinData, @nByteNum,1)  & @nMask) = @nMask
since the bitwise operation is performed on different byte offsets wouldn't that require a statement executed for every bit position?

For course.  For each bit position that you wanted to check (there are 64,000 such positions in an 8,000-byte field), it would need to examine each row of the table.  There is no getting around that.  You could set up a series of ORs to avoid repeatedly reading all rows:

SELECT * FROM MyTable
      WHERE  (SUBSTRING( yBinData, @nByteNum1,1)  & @nMask_1) = @nMask_1
      OR  (SUBSTRING( yBinData, @nByteNum_2,1)  & @nMask_2) = @nMask_2
      OR  (SUBSTRING( yBinData, @nByteNum_3,1)  & @nMask_3) = @nMask_3

And if two of the bits are very close together (in the same byte or perhaps the same 32-bit chunk) you could create a smarter mask that would check for both bits in one comparison.  But even so, the DBMS is going to be doing a LOT of work, in a way that it is not specifically designed to do.

=-==-=-=-=-=-=-
Frankly if this will be a common operation and if performance is the critical issue -- for instance looking for a number of specific patterns that may be at any part of the the data (such as looking for a cat in a black-and-white image), then I'd consider reading the data into memory and using a good general-purpose prograamming language -- such as C++ -- to do the scanning.

If performance is *REALLY* critical (eg, if you will be looking for hundrds of complex bit patterns in millions of image scanlines), I'd even consider using Assembly Language to access the special-purpose CPU opcodes (MMX, SSE) that are designed for that very operation.

Perhaps if you described your project in more detail, I can help you think of ways to accomplish your actual goal.

-- Dan
--going to use a udf that compares binary values and can be used in a where clause. the udf seems to work ok on it's own but incorrectly in where clause

--udf
CREATE FUNCTION dbo.udf_compareMask(@mask VARBINARY(8000),@compareMask VARBINARY(8000))
RETURNS INT
AS
BEGIN
DECLARE @result INT
DECLARE @counter INT
SET @counter = 0
WHILE @counter <= LEN(@mask)
BEGIN
IF SUBSTRING(@mask,@counter,1)&CAST(SUBSTRING(@compareMask,@counter,1) AS INT) >= 1
BEGIN SET @result = 1 BREAK END
ELSE IF SUBSTRING(@mask,@counter,1)|CAST(SUBSTRING(@compareMask,@counter,1) AS INT) = 0
BEGIN SET @result = 1 END
ELSE
BEGIN SET @result = 0 END                  
SET @counter = @counter + 1
END
RETURN @result
END

--function works fine on it's own
--return 1 when a bit matches
SELECT dbo.udf_compareMask(0x0000000000000001,0x0000000000000001)
SELECT dbo.udf_compareMask(0x8000000000000000,0x8000000000000000)
SELECT dbo.udf_compareMask(0x2000000010000002,0x4000000010000000)
--returns 0 when no matches
SELECT dbo.udf_compareMask(0x8000000000000002,0x4000000000000001)
SELECT dbo.udf_compareMask(0x2000000010000002,0x4000000080000008)

--table 4 test
CREATE TABLE [dbo].[tab_recordMaster] (
      [recordMasterID] [int] IDENTITY (1, 1) NOT NULL ,
      [recordMasterAttribute] [binary] (8) NOT NULL ,
) ON [PRIMARY]
GO
--insert test data
INSERT INTO tab_recordMaster (recordMasterAttribute) VALUES (0x0000000000000000)
INSERT INTO tab_recordMaster (recordMasterAttribute) VALUES (0x0000000000000001)
INSERT INTO tab_recordMaster (recordMasterAttribute) VALUES (0x8000000000000000)
INSERT INTO tab_recordMaster (recordMasterAttribute) VALUES (0x8000000040000110)

--works on last byte
DECLARE @bitmaskCheck VARBINARY(8000)
SET @bitmaskCheck = 0x0000000000000001
SELECT recordMasterAttribute,dbo.udf_compareMask(recordMasterAttribute,@bitmaskCheck)
FROM tab_recordMaster WHERE dbo.udf_compareMask(recordMasterAttribute,@bitmaskCheck) = 1
GO
--fails on all others
DECLARE @bitmaskCheck VARBINARY(8000)
SET @bitmaskCheck = 0x0000000000000100
SELECT recordMasterAttribute,dbo.udf_compareMask(recordMasterAttribute,@bitmaskCheck)
FROM tab_recordMaster WHERE dbo.udf_compareMask(recordMasterAttribute,@bitmaskCheck) = 1
GO
figured it out.. what i was trying to do is store row attributes as 'bit pisitions' in a mask.

--select sproc
CREATE PROCEDURE prc_selectRecordMaster(@recordType INT,@string VARCHAR(4000)) AS
DECLARE @bitmask BINARY(8)
DECLARE @bitmaskCheck VARBINARY(8000)
SET @bitmask = 0x00
DECLARE @bitposition INT
CREATE TABLE #bitpositions (value INT)
INSERT #bitpositions EXEC prc_parseDelimitedString @string DECLARE bitposition_cursor CURSOR FOR
SELECT value FROM #bitpositions
OPEN bitposition_cursor
FETCH NEXT FROM bitposition_cursor INTO @bitposition
WHILE @@FETCH_STATUS=0
BEGIN
EXEC prc_updateBitmaskOn @bitmask,@bitposition,@bitmask OUT
FETCH NEXT FROM bitposition_cursor INTO @bitposition
END
CLOSE bitposition_cursor DEALLOCATE bitposition_cursor DROP TABLE #bitpositions
DECLARE @counter INT
SET @counter = 0
WHILE @counter <= LEN(@bitmask)/4-1
BEGIN
IF @bitposition > LEN(@bitmask)*8 BREAK
IF @counter = 0
SET @bitmaskCheck = SUBSTRING(@bitmask,0,5)
ELSE
SET @bitmaskCheck = @bitmaskCheck + SUBSTRING(@bitmask,@counter*4+1,4)
SET @counter = @counter + 1
END
PRINT @bitmaskCheck
SELECT * FROM tab_recordMaster WHERE recordMasterType = 1 AND
dbo.udf_compareMask(recordMasterAttribute,@bitmaskCheck) = 1
GO

--compare function
CREATE FUNCTION dbo.udf_compareMask(@mask VARBINARY(8000),@compareMask VARBINARY(8000))
RETURNS INT
AS
BEGIN
DECLARE @result INT
DECLARE @counter INT
SET @counter = 0
WHILE @counter <= LEN(@mask)
BEGIN
IF SUBSTRING(@mask,@counter,1)&CAST(SUBSTRING(@compareMask,@counter,1) AS INT) >= 1
BEGIN SET @result = 1 BREAK END
ELSE IF SUBSTRING(@mask,@counter,1)|CAST(SUBSTRING(@compareMask,@counter,1) AS INT) = 0
BEGIN IF @counter <> LEN(@mask) BEGIN SET @result = 0 END ELSE BEGIN SET @result = 0 END END
ELSE
BEGIN SET @result = 0 END
SET @counter = @counter + 1
END
RETURN @result
END
ASKER CERTIFIED SOLUTION
Avatar of DanRollins
DanRollins
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
i figured it out but i'll go ahead and give you the points for your time..

lol.. no secret. what i have is a table that requires every row to have 1000s of attributes so figured i'd use a mask.

to select the rows i was using substring commands in the where clause. i just wanted to clean that up a bit

thx 4 ur help