Solved

Using Int64 as a bit container

Posted on 2001-08-13
16
1,648 Views
Last Modified: 2012-06-27
Hi there,


I've recently written a DES (cryptography) in Delphi which uses a record to store each block (this record contains a BitCount field and an array of Bytes for the actual data). This record-method is really slow because I access these bits ALOT in sevral nested loops. I've also looked at the TBits class in VCL but its also too slow for me. This is why I want to use the Int64 data type as a bit container.

I intend to use it like this:

var
  Container: Int64;
begin
  Container := 0;
  //set bit number 8
  Container := Container or BinPwr[8];
  //read bit number 8
  if Container AND BinPwr[8] > 0 then
    ShowMessage('This happens if the 8th bit is set');
end;


This method is fast enough if I use a pre-calculated BinPwr[] array which contains the binary powers, eg; 1, 2, 4, 8, 16, 32 etc etc. Since I need to access up to 64 different bits I also need a BinPwr[] array with 64 elements.

My problem atm is; for nine days I've tried to implement this little (very simple) bit container system. But it does not work, the Int64 refuses to hold 64 different bits -- I only manage to save 63 bits in it.

Since the Int64 integer type is actually signed the last entry in the BinPwr[] should be equal to
-9223372036854775808 which is the largest negative integer that can be stored in an Int64.

My first problem was that I could not type
-9223372036854775808 in the Delphi IDE. It said that this number was "Integer constant to large". But I know my maths and this *should* work because ?2^63 =
-9223372036854775808 and strangely I can avoid this by writing -9223372036854775807-1 or Low(Int64) instead?! I suspect this is an IDE bug. If I then execute ShowMessage(IntToStr(i)); the message box clearly says -9223372036854775808 so apparently Delphi can handle this number but the IDE (the pre-processor or token-parser) rejects it.

And when I try to execute:

var
  i: Int64;
begin
  i := 0;
  i := i or -9223372036854775807-1;
  if i and -9223372036854775807-1 then
    ShowMessage('This *SHOULD* happend!!');
end;

The above message box does NOT appear!??!?! Now I'm getting really confused here. Inserting any other number (instead of -9223372036854775807-1) makes it work, but that's irrelevant.

-----

Anyway, I will give the points to any one hero who will give me a working example of a bit container which can:

(1) show the bits in a string; eg a function which takes a Int64 and shows the 64 bits in 0s and 1s. something like bitsToStr()

(2) set and read 64 different bits

(3) is correctly compatible with the shl,shr operators. Meaning that if I set bit 8 then executes a shl on it, the "1" should move to the left when I re-execute the showmessage(bitsToStr(i)) function.


I've worked with network bit-order, motorola bitorder, intel bitorder and signed and unsigned and blah blah and this bit thing it really starting to get to me. For nine days I've had nothing but failures, this tends to wear a person out. I'm sick and tired of bits. Please help me.

If you are unsure of what I'm asking for, please post a comment.

I have more points if needed I REALLY REALLY want this one solved.


/m
0
Comment
Question by:requiem
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 6
  • 2
  • +1
16 Comments
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6379908
Hi, man.

I can implement it, but right now I'm a bit busy. Maybe someone will do it. Just as a comment: try

const j=$FFFFFFFFFFFFFFFF;

procedure TForm1.Button1Click(Sender: TObject);
var
 i: Int64;
begin
 i := 0;
 i := i or j;
 if (i and j) <> 0 then
   ShowMessage('This *SHOULD* happend!!');
end;

This show a message saying "This *SHOULD* happend!!"
:-)

Rgds,
Frodo
0
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6379939
Oh, my error. Constant not big enough for you. Sorry

Rgds,
Frodo
0
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6379950
In fact I think you can't use all the 64 bits in int64 because one of them is a sign-bit.

Rgds,
Frodo
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6380027
Well, that works:

var j : array[0..63] of Int64;

procedure TForm1.Button1Click(Sender: TObject);
var
 i : int64;
begin
 i := 0;
 i := i or j[63];
 if (i and j[63]) <> 0 then
   ShowMessage('This *SHOULD* happend!!'#13+IntToStr(j[63]));
end;


procedure TForm1.FormCreate(Sender: TObject);
var i:integer;
begin
  j[0]:=1;
  for i:=1 to 63 do
    j[i]:=j[i-1] shl 1;
end;

The "constants" are calculated only once. That's fast :)

Rgds,
Frodo
0
 
LVL 20

Expert Comment

by:Madshi
ID: 6380073
This one should do it:

var
  BinPwr : array [0..63] of int64 =
    ($0000000000000001, $0000000000000002, $0000000000000004, $0000000000000008,
     $0000000000000010, $0000000000000020, $0000000000000040, $0000000000000080,
     $0000000000000100, $0000000000000200, $0000000000000400, $0000000000000800,
     $0000000000001000, $0000000000002000, $0000000000004000, $0000000000008000,
     $0000000000010000, $0000000000020000, $0000000000040000, $0000000000080000,
     $0000000000100000, $0000000000200000, $0000000000400000, $0000000000800000,
     $0000000001000000, $0000000002000000, $0000000004000000, $0000000008000000,
     $0000000010000000, $0000000020000000, $0000000040000000, $0000000080000000,
     $0000000100000000, $0000000200000000, $0000000400000000, $0000000800000000,
     $0000001000000000, $0000002000000000, $0000004000000000, $0000008000000000,
     $0000010000000000, $0000020000000000, $0000040000000000, $0000080000000000,
     $0000100000000000, $0000200000000000, $0000400000000000, $0000800000000000,
     $0001000000000000, $0002000000000000, $0004000000000000, $0008000000000000,
     $0010000000000000, $0020000000000000, $0040000000000000, $0080000000000000,
     $0100000000000000, $0200000000000000, $0400000000000000, $0800000000000000,
     $1000000000000000, $2000000000000000, $4000000000000000, $8000000000000000);

Regards, Madshi.
0
 
LVL 4

Expert Comment

by:fva
ID: 6380086
DES is left/right based. Why don't you stick to the "classical" approach to DES on 32-bit machines and go

packed record
   left_part:integer;
   right_part:integer;
end;

then base all your code on this approach.

The int64 might be handled internally still as two 32-bit by the compiler.

F.
0
 
LVL 20

Expert Comment

by:Madshi
ID: 6380109
But if you stick with int64, this might be faster in the future, when going to real 64bit CPUs...  :-)

>> (1) show the bits in a string; eg a function which takes a Int64 and shows the 64 bits in 0s and 1s. something like bitsToStr()

function bitsToStr(bits: int64) : string;
begin
  SetLength(result, 64);
  for i1 := 64 downto 1 do begin
    result[i1] := chr(ord('0') + bits and 1);
    bits := bits shr 1;
  end;
end;

>> (2) set and read 64 different bits

procedure SetBit(var bits: int64; bit: integer);
begin
  bits := bits or BinPwr[bit];
end;

procedure ClearBit(var bits: int64; bit: integer);
begin
  bits := bits and ($FFFFFFFFFFFFFFFF xor BinPwr[bit]);
end;

procedure GetBit(bits: int64; bit: integer) : boolean;
begin
  result := bits and BinPwr[bit] <> 0;
end;

>> (3) is correctly compatible with the shl,shr operators. Meaning that if I set bit 8 then executes a shl on it, the "1" should move to the left when I re-execute the showmessage(bitsToStr(i)) function.

Should be this way.

Regards, Madshi.
0
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6380123
Here is a BitsToStr function:

function BitsToStr(n : int64) : string;
var i:integer;
    buf:String;
begin
  buf := '';
  for i := 0 to 63 do
  begin
    if (n and j[i]) = 0 then
      buf := '0' + buf
    else
      buf := '1' + buf;
  end;
  result := buf;
end;
0
 
LVL 20

Accepted Solution

by:
Madshi earned 300 total points
ID: 6380125
Sorry, little correction, tested now:

function bitsToStr(bits: int64) : string;
var i1 : integer;
begin
  SetLength(result, 64);
  for i1 := 64 downto 1 do begin
    result[i1] := chr(ord('0') + bits and 1);
    bits := bits shr 1;
  end;
end;

procedure SetBit(var bits: int64; bit: integer);
begin
  bits := bits or BinPwr[bit];
end;

procedure ClearBit(var bits: int64; bit: integer);
begin
  bits := bits and ($FFFFFFFFFFFFFFFF xor BinPwr[bit]);
end;

function GetBit(bits: int64; bit: integer) : boolean;
begin
  result := bits and BinPwr[bit] <> 0;
end;
0
 
LVL 4

Expert Comment

by:fva
ID: 6380167
"But if you stick with int64, this might be faster in the future, when going to real 64bit CPUs...  :-)"

Well, true. And by that time it'll be a very fast demo for a long-deprecated algorithm :) Or is it already as such?

F.
0
 
LVL 20

Expert Comment

by:Madshi
ID: 6380181
(-:
0
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6380211
Madshi, don't tell me you wrote the constants "manualy" ;-))

Rgds,
Frodo
0
 
LVL 20

Expert Comment

by:Madshi
ID: 6380254
:-)  Kind of manually. I wrote one line with only zeros, copied this line 16x, then I filled the "1" into the first block from the bottom left to the right top. Same with the other 3 blocks. Only some seconds work...

P.S: One hint on a side note (I hope you don't mind?). If you want to fill a string, from which you know the destination length already before the filling, it's much faster to use SetLength before. My "bitsToStr" function is probably several times faster than yours, because mine is avoiding steadily reallocating...  :-)
0
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6380298
10x, sounds logical :)

Every time I add another char it's like calling SetLength to grow the dynamic string, I guess.

Rgds,
Frodo
0
 
LVL 1

Author Comment

by:requiem
ID: 6381684
Many times per day I wonder; who is madshi? what is madshi? how can he be so extremely good at this?

Once again madshi, you solved my problems. The problem was not the bit container but in search of the bug I had modified every thing into madness and when I inserted your bitcontainer in my project it all made sense. My real problem was related to the weird bitorder used by the NSA in FIPS-specifikation of DES. They call the left-most bit 1 and the right-most 64 and many other strange things. And there was a few other bugs too.

Anyway my code works, and that's what counts.

You are now in the "credits"-section of this project, which will be released under MPL (open-source) sometime later on. Probably through JEDI.

As for "long-deprecated" algorithms, I intend to use the DES implementation for a 3DES EDE unit (which is the final product). This may later my used in a PGP or SSH implementation (two projects I would want to write for Delphi someday).

So, thanks to all of ya. I love EE! :)



/m
0
 
LVL 20

Expert Comment

by:Madshi
ID: 6383002
Hi Frodo!

>> Every time I add another char it's like calling SetLength to grow the dynamic string, I guess.

Yep, exactly...

Hi reqiuem!

>> Many times per day I wonder; who is madshi? what is madshi? how can he be so extremely good at this?

Hah!  :-)  Thank you...

>> You are now in the "credits"-section of this project

Great! Thanx...  (-:

Regards, Madshi.
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Dynamically Created Query 3 70
DBCtrlGrid, Delphi, Scroll 7 33
Firemonkey BASS_Init into a thread 17 57
TlistView is Really heavy on Android 3 21
A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
Introduction Raise your hands if you were as upset with FireMonkey as I was when I discovered that there was no TListview.  I use TListView in almost all of my applications I've written, and I was not going to compromise by resorting to TStringGrid…
A short tutorial showing how to set up an email signature in Outlook on the Web (previously known as OWA). For free email signatures designs, visit https://www.mail-signatures.com/articles/signature-templates/?sts=6651 If you want to manage em…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

726 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question