Solved

Using Int64 as a bit container

Posted on 2001-08-13
16
1,612 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
  • 7
  • 6
  • 2
  • +1
16 Comments
 
LVL 2

Expert Comment

by:FrodoBeggins
Comment Utility
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
Comment Utility
Oh, my error. Constant not big enough for you. Sorry

Rgds,
Frodo
0
 
LVL 2

Expert Comment

by:FrodoBeggins
Comment Utility
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
 
LVL 2

Expert Comment

by:FrodoBeggins
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 20

Accepted Solution

by:
Madshi earned 300 total points
Comment Utility
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
Comment Utility
"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
Comment Utility
(-:
0
 
LVL 2

Expert Comment

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

Rgds,
Frodo
0
 
LVL 20

Expert Comment

by:Madshi
Comment Utility
:-)  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
Comment Utility
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
Comment Utility
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
Comment Utility
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

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Suggested Solutions

The uses clause is one of those things that just tends to grow and grow. Most of the time this is in the main form, as it's from this form that all others are called. If you have a big application (including many forms), the uses clause in the in…
Have you ever had your Delphi form/application just hanging while waiting for data to load? This is the article to read if you want to learn some things about adding threads for data loading in the background. First, I'll setup a general applica…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…
You have products, that come in variants and want to set different prices for them? Watch this micro tutorial that describes how to configure prices for Magento super attributes. Assigning simple products to configurable: We assigned simple products…

763 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

Need Help in Real-Time?

Connect with top rated Experts

7 Experts available now in Live!

Get 1:1 Help Now