the absolute bleed edge fastest way to strip out bits from 4 bytes of hex

I am looking for the absolute top dog in speed to do the following

If i have an 8 byte char for example

test = {a a a a a a a a }

I need to be able to break it down into two pieces

x bits to y bits

and

m bits to n bits

So far i have done a speed test on an old process like this

answer = dec2bin(hex2dec(strcat(word_1,word_2)));

answer = answer(1:22);

answer = bin2dec(answer);

Then i ran a speed test on a newer function

hex2binaryvector

Then using the bi2de function that i beleive is newer

Im seeing a 10X slow down in the new function

Can anyone confirm?

[DGM]

Assuming these are character vectors, you can get a chunk of speed by just using

[word_1,word_2]

instead of strcat().

Given that dec2bin() and hex2dec() seem to be doing the math in m-code, I imagine you can roll a pedestrian hex2bin() function that's faster than the two together, but maybe not by much.

Answer 1

[DGM]

There's this.

word_1 = 'DEAD';
word_2 = 'BEEF';

answer = hex2bin([word_1,word_2]);
answer = bin2dec(answer(1:22));

Using the simplified concatenation and the combined hex2bin conversion reduces execution time by about 70% for me. There are probably faster ways yet, but eh. I'll leave that to others ... probably.

Attached is a modified version of this FEX submission:

https://fr.mathworks.com/matlabcentral/fileexchange/24282-hexadecimal-to-binary

I thought it'd be quick enough to just grab it, but I ended up changing it to output character vectors and be case-insensitive. It's not really any faster.

If you use the attached version of bin2dec(), you can squeeze a bit more out. About the fastest I've managed is an 80% reduction in time. EDIT: updated to fix a dumb error! I guess I oversimplified a bit too much and didn't catch it.

[Robert Scott]

Thanks!

So your telling me your version of hex2bin is faster then the matlab one?

Im going to give that a speed test myself

[Jan]

@DGM: A 25% faster and leaner version using a look up table:

n    = 1e5;
data = sprintf('%x', 123456);
tic;
for k = 0:n, b = hex2bin(data); end
toc

Elapsed time is 0.766541 seconds.

hex2bin_2('BEEF');  % Warm-up, needed in Matlab online only
tic;
for k = 0:n, b = hex2bin_LUT(data); end
toc

Elapsed time is 0.573024 seconds.

function bin=hex2bin(x)
% Y = HEX2BIN(X)
% 
% X is a hexadecimal number (character vector, case-insensitive)
% Y is a binary number (character vector)
% 
% based on this FEX submission:
% https://fr.mathworks.com/matlabcentral/fileexchange/24282-hexadecimal-to-binary

hex = lower(x);
bin = repmat('0',[1 numel(hex)*4]);
for i = 1:length(hex)
	switch hex(i)
		case 'f'
			bin((i*4)-3:i*4)='1111';
		case 'e'
			bin((i*4)-3:i*4)='1110';
		case 'd'
			bin((i*4)-3:i*4)='1101';
		case 'c'
			bin((i*4)-3:i*4)='1100';
		case 'b'
			bin((i*4)-3:i*4)='1011';
		case 'a'
			bin((i*4)-3:i*4)='1010';
		case '9'
			bin((i*4)-3:i*4)='1001';
		case '8'
			bin((i*4)-3:i*4)='1000';
		case '7'
			bin((i*4)-3:i*4)='0111';
		case '6'
			bin((i*4)-3:i*4)='0110';
		case '5'
			bin((i*4)-3:i*4)='0101';
		case '4'
			bin((i*4)-3:i*4)='0100';
		case '3'
			bin((i*4)-3:i*4)='0011';
		case '2'
			bin((i*4)-3:i*4)='0010';
		case '1'
			bin((i*4)-3:i*4)='0001';
		case '0'
			bin((i*4)-3:i*4)='0000';
	end
end
end

function bin = hex2bin_LUT(x)
persistent LUT
if isempty(LUT)
    LUT = repmat(' ', 4, 103);
    for c = '0123456789abcdefABCDEF'
        LUT(:, double(c)) = dec2bin(sscanf(c, '%x'), 4).';
    end
end

bin = reshape(LUT(:, double(x)), 1, []);
end

[DGM]

Nice!

I've been finding lately how many of the things I've learned have since left my mind. I spent much time using LUTs in C to avoid arithmetic on feeble microcontrollers, but I've since just forgotten that something with a small domain like this would be a prime use-case.

Answer 2

[Walter Roberson]

The absolute top dog in speed is to have (y-x+n-m+2) different 8 dimensional lookup tables, each of which is (102 x 102 x 102 x 102 x 102 x 102 x 102 x 102) entries and each of which returns one bit. If you can promise upper case instead of lower case then the dimensions can be 70 instead of 102.

The memory requirements can be drastically reduced by very simple calculations, but that will not give you absolute top dog performance.

This approach requires more memory than any publicly known x64 implementation can use (the public x64 design only defines 48 address lines), but so what? It is faster than the alternatives.

When you ask for absolute top dog, you are asking for all of the safety measures to be taken out, including safety precautions against it requiring more hardware than you can possibly afford.

[Robert Scott]

really intertesting results Walter

I just got rid of all my hextobinaryvector calls and just went back to the code that is actually 5 lines longer and got a 10X speedup

Apparently, hextobinaryvector has to much overhead

answer = dec2bin(hex2dec(strcat(word_1,word_2)));

answer = answer(1:22);

answer = bin2dec(answer);

This worked much much faster