TweetFollow Us on Twitter

CRC
Volume Number:9
Issue Number:4
Column Tag:Pascal Workshop

CRCs in Pascal

Checking your data when transferring from one computer to another

By Mark R. Drake, Minneapolis, Minnesota

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

About the author

Mark R. Drake is a programmer for Detector Electronics in Minneapolis, Minnesota. His main areas of interest are communications and industrial computer control.

When transferring data from one computer to another via serial devices, the careful application of data integrity checking is required to ensure the validity of the data. In the industrial computer world, data that is transferred from one computer to another may be controlling a large piece of machinery and if the data contains an error and the error is not detected, damage to the machinery and injury to personal may occur.

Several different methods of data error checking are used, but we will cover the one that is used most often in the Macintosh world.

One of the best data error checking methods that can be used is the “Cyclical Redundancy Check” (CRC). Without getting into the mathematical reasons why CRC is good, we will just let stand that it offers a high level of protection. If you want more information on the mathematical properties of CRC generation, your local library should have plenty of information.

You can calculate a CRC check value on a block of bytes by performing a few initializations and then test each bit in each byte to determine if you do one of two possible operations. Refer to Example One. You would pass each byte in the block to the “DoCrcCal” procedure. After you have tested all of the bytes in the block, you will have the CRC check value. As you can see, that method is very slow because you have to test every bit and then do a logical operation to decide which operation to perform. On a Macintosh with a 2400 baud modem, you will not notice the loss of time. With any higher baud rates the lost time is substantial.

Example One
var
 crcCC: longint;

procedure DoCrcCal(theData:longint);
 const
 hiBitMask = $08000;
 polyCCITT = $01021; {CRC-CCITT polynomial}
 polyCRC16 = $0A001; {CRC16 polynomial}
 var
 loop: integer;
 tempdata, crcXor: longint;
begin
 crcCC:= BitXor(BitShift(theData,8),crcCC);
 for loop := 1 to 8 do
 begin
    crcXor := BitAnd(crcCC,hiBitMask);
    if BitTst(@crcXor,16) then
 crcCC:=BitXor(BitShift(crcCC,1),polyCCITT);
    else
     crcCC := BitShift(crcCC,1);
   end;
 crcCC := BitAnd(crcCC,65535);
end;

We can overcome the problem by generating a “CRC lookup table”. Refer to Example Two. We can generate the table and save a great deal of time calculating our CRC check value by doing only two bit shifts per byte compared to eight as required in the first example. Example two is the generation of the lookup table. The generation of the table is calculating a check value in the table for the numbers 0-255. The calculation is the same as the procedure in figure one, but the big difference is that you create this table before you start the transfer.

Table one is a listing of what the table should contain after it is created using the CRC-CCITT polynomial. CRC-CCITT is the polynomial used in Macintosh communications by most vendors.

Example Two
var
 crcTable: array[0..255] of longint;

procedure MakeCRCTable;
 const
 hiBitMask = $08000;
 polyCCITT = $01021; {CRC-CCITT polynomial}
 polyCRC16 = $0A001; {CRC16 polynomial}
 var
 crcCC,crcXor,i,tableCounter: longint;
 loop: byte;
begin
 for tableCounter := 0 to 255 do
 begin
 crcCC := 0;{must be set to zero}
 crcCC:=BitXor(BitShift(tableCounter,8),crcCC);
 for loop := 1 to 8 do
 begin
 crcXor := BitAnd(crcCC,hiBitMask);    if BitTst(@crcXor,16) then
 crcCC:=BitXor(BitShift(crcCC,1),polyCCITT)  
 else
 crcCC := BitShift(crcCC,1);
 end;
 crcTable[tableCounter]:=BitAnd(crcCC,65535);      
 end;
end;

The usage of the lookup table is shown in Example Three. For serial communications I always use a packed array of bytes. The byte that I want to calculate is contained in “byteRec[1]”. I calculate the CRC check value on each byte as the byte is received. The processor can perform thousands of operations while the next byte is coming in the serial controller. So, first I put the data byte into a longint. Then we want to XOR the upper eight bits of the current value of the CRC with the data byte. First shift the current CRC eight bits right and do an XOR with the data byte. This is the value that we are going to use to get the precalculated CRC from the lookup table. Then shift eight bits left and XOR the value from the table with the current value of the CRC. You then have the CRC check value. That’s it. The BitAnd’s are for safety.

Example Three
var
 tempdata,crc,crcCC,temp1,temp2: longint;

crcCC := 0; {must be set to zero}

{when you start to calculate the CRC you must}
{set the crcCC variable to zero}
{it must be set to zero before every new}
{CRC that you calculate}

tempData := byteRec[1];   {the byte to use}
crcCC := BitAnd(BitXor(BitShift(crcCC,8), crcTable[BitAnd(BitXor(BitShift(crcCC,-8), 
tempData),255)]),65535);

{the above broken into separate lines}
tempData := byteRec[1];   {the byte to use}
temp1:=BitShift(crcCC,-8);
temp2 := BitXor(temp1,tempData);
temp2 := BitAnd(temp2,255); {safety}
crc := crcTable[temp2];
temp1 := BitShift(crcCC,8);
temp2 := BitXor(temp1,crc)
crcCC := BitAnd(temp2,65535); {safety}

Testing the speed

The following listing is a program to test the speed of the two methods of CRC calculation. The two procedures that perform the test are called ten times. I have used the Think Pascal profiler to determine the speed. Refer to the Results table. The test was performed on a standard MacPlus. The results of the profiler have been saved to a file in the program.

program Main;

 uses
  Profiler;

 var
  crcTable: array[0..255] of longint;
  crcCC1, crcCC2: longint;
  x: integer;

 procedure DoCrcBitCalc;
  const
   hiBitMask = $08000;
   polyCCITT = $01021;
   polyCRC16 = $0A001;
  var
   loop, i: integer;
   tempdata, crcXor: longint;
 begin
  crcCC2 := 0;
  for i := 0 to 255 do
   begin
    tempData := i;
    crcCC2:=BitXor(BitShift(tempData,8), crcCC2);
    for loop := 1 to 8 do
     begin
      crcXor := BitAnd(crcCC2, hiBitMask);
      if BitTst(@crcXor, 16) then
       crcCC2:=BitXor(BitShift(crcCC2,1), polyCCITT)
      else
       crcCC2 := BitShift(crcCC2, 1);
     end;
    crcCC2 := BitAnd(crcCC2, 65535);
   end;
 end;

 procedure DoTableTest;
  var
   i: integer;
   tempData, crc: longint;
 begin
  crcCC1 := 0;
  for i := 0 to 255 do
   begin
    tempData := i;
    crcCC1 := BitAnd(BitXor(BitShift(crcCC1,8),
      crcTable[BitAnd(BitXor(BitShift(crcCC1,-8),
      tempData),255)]),65535);
   end;
 end;

 procedure MakeCRCTable;
  const
   hiBitMask = $08000;
   polyCCITT = $01021;  {CRC-CCITT polynomial}
   polyCRC16 = $0A001;  {CRC16 polynomial}
  var
   crcCC, crcXor, i, tableCounter: longint;
   loop: byte;
 begin
  for tableCounter := 0 to 255 do
   begin
    crcCC := 0;  {must be set to zero}
  crcCC:=BitXor(BitShift(tableCounter,8),                      
 crcCC);
    for loop := 1 to 8 do
     begin
      crcXor:=BitAnd(crcCC,hiBitMask);
      if BitTst(@crcXor, 16) then
       crcCC:=BitXor(BitShift(crcCC,1),polyCCITT)              
  else
       crcCC := BitShift(crcCC, 1);                      end;
    crcTable[tableCounter]:=BitAnd(crcCC, 65535);
   end;
 end;

begin
 MakeCRCTable;
 for x := 0 to 99 do
  begin
   DoCrcBitCalc;
   DoTableTest;
  end;
 DumpProfileToFile(‘CRCTestFile’);
end.

Results Table

THINK Pascal Procedure Profile

All time is measured in milliseconds and rounded down to the nearest 
millisecond.
Elapsed Time  =   26176
Measured Time =   26111
Total Calls   =      21

Routine Min Max Avg Total % Times

Name Time Time Time Time Time Called

MAKECRCT 2157 2157 2157 2157 8.26 1

DOCRCBIT 2144 2153 2146 21465 82.21 10

DOTABLET 248 250 248 2489 9.53 10

As the test shows, the CRC table lookup method is more than eight times faster than the test every bit method. The correct CRC check value for 0-255 using the CRC-CCITT polynomial is $7E55.

Conclusion

The lookup table method has the speed overhead of creating the table, but this overhead is offset by the amount of data that is transferred or is to be used to calculate the check value. The lookup table method is much easier to work with. The code size and data size is greater with the lookup table method, but I think the speed advantage is so great that the extra words of code and data are put to good use.

Table One
   |  -0- -1-  -2- -3-  |
000: 0000 0000 0000 1021 0000 2042 0000 3063
010: 0000 4084 0000 50A5 0000 60C6 0000 70E7
020: 0000 8108 0000 9129 0000 A14A 0000 B16B
030: 0000 C18C 0000 D1AD 0000 E1CE 0000 F1EF
040: 0000 1231 0000 0210 0000 3273 0000 2252
050: 0000 52B5 0000 4294 0000 72F7 0000 62D6
060: 0000 9339 0000 8318 0000 B37B 0000 A35A
070: 0000 D3BD 0000 C39C 0000 F3FF 0000 E3DE
080: 0000 2462 0000 3443 0000 0420 0000 1401
090: 0000 64E6 0000 74C7 0000 44A4 0000 5485
0A0: 0000 A56A 0000 B54B 0000 8528 0000 9509
0B0: 0000 E5EE 0000 F5CF 0000 C5AC 0000 D58D
0C0: 0000 3653 0000 2672 0000 1611 0000 0630
0D0: 0000 76D7 0000 66F6 0000 5695 0000 46B4
0E0: 0000 B75B 0000 A77A 0000 9719 0000 8738
0F0: 0000 F7DF 0000 E7FE 0000 D79D 0000 C7BC
100: 0000 48C4 0000 58E5 0000 6886 0000 78A7
110: 0000 0840 0000 1861 0000 2802 0000 3823
120: 0000 C9CC 0000 D9ED 0000 E98E 0000 F9AF
130: 0000 8948 0000 9969 0000 A90A 0000 B92B
140: 0000 5AF5 0000 4AD4 0000 7AB7 0000 6A96
150: 0000 lA71 0000 0A50 0000 3A33 0000 2A12
160: 0000 DBFD 0000 CBDC 0000 FBBF 0000 EB9E
170: 0000 9B79 0000 8B58 0000 BB3B 0000 AB1A
180: 0000 6CA6 0000 7C87 0000 4CE4 0000 5CC5
190: 0000 2C22 0000 3C03 0000 0C60 0000 1C41
lA0: 0000 EDAE 0000 FD8F 0000 CDEC 0000 DDCD
lB0: 0000 AD2A 0000 BD0B 0000 8D68 0000 9D49
lC0: 0000 7E97 0000 6EB6 0000 5ED5 0000 4EF4
lD0: 0000 3E13 0000 2E32 0000 1E51 0000 0E70
lE0: 0000 FF9F 0000 EFBE 0000 DFDD 0000 CFFC
lF0: 0000 BFlB 0000 AF3A 0000 9F59 0000 8F78
200: 0000 9188 0000 8lA9 0000 BlCA 0000 A1EB
210: 0000 Dl0C 0000 C12D 0000 F14E 0000 E16F
220: 0000 1080 0000 00A1 0000 30C2 0000 20E3
230: 0000 5004 0000 4025 0000 7046 0000 6067
240: 0000 83B9 0000 9398 0000 A3FB 0000 B3DA
250: 0000 C33D 0000 D31C 0000 E37F 0000 F35E
260: 0000 02Bl 0000 1290 0000 22F3 0000 32D2
270: 0000 4235 0000 5214 0000 6277 0000 7256
280: 0000 B5EA 0000 A5CB 0000 95A8 0000 8589
290: 0000 F56E 0000 E54F 0000 D52C 0000 C50D
2A0: 0000 34E2 0000 24C3 0000 14A0 0000 0481
2B0: 0000 7466 0000 6447 0000 5424 0000 4405
2C0: 0000 A7DB 0000 B7FA 0000 8799 0000 97B8
2D0: 0000 E75F 0000 F77E 0000 C71D 0000 D73C
2E0: 0000 26D3 0000 36F2 0000 0691 0000 16B0
2F0: 0000 6657 0000 7676 0000 4615 0000 5634
300: 0000 D94C 0000 C96D 0000 F90E 0000 E92F
310: 0000 99C8 0000 89E9 0000 B98A 0000 A9AB
320: 0000 5844 0000 4865 0000 7806 0000 6827
330: 0000 18C0 0000 08E1 0000 3882 0000 28A3
340: 0000 CB7D 0000 DB5C 0000 EB3F 0000 FB1E
350: 0000 8BF9 0000 9BD8 0000 ABBB 0000 BB9A
360: 0000 4A75 0000 5A54 0000 6A37 0000 7A16
370: 0000 0AFl 0000 lAD0 0000 2AB3 0000 3A92
380: 0000 FD2E 0000 ED0F 0000 DD6C 0000 CD4D
390: 0000 BDAA 0000 AD8B 0000 9DE8 0000 8DC9
3A0: 0000 7C26 0000 6C07 0000 5C64 0000 4C45
3B0: 0000 3CA2 0000 2C83 0000 1CE0 0000 0CC1
3C0: 0000 EFlF 0000 FF3E 0000 CF5D 0000 DF7C
3D0: 0000 AF9B 0000 BFBA 0000 8FD9 0000 9FF8
3E0: 0000 6E17 0000 7E36 0000 4E55 0000 5E74
3F0: 0000 2E93 0000 3EB2 0000 0EDl 0000 1EFO
   |  -252- -253--254-  -255- |

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Lyn 1.5.11 - Lightweight image browser a...
Lyn is a lightweight and fast image browser and viewer designed for photographers, graphic artists and Web designers. Featuring an extremely versatile and aesthetically pleasing interface, it... Read more
NeoOffice 2014.11 - Mac-tailored, OpenOf...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
LaunchBar 6.4 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... Read more
Remotix 3.1.4 - Access all your computer...
Remotix is a fast and powerful application to easily access multiple Macs (and PCs) from your own Mac. Features Complete Apple Screen Sharing support - including Mac OS X login, clipboard... Read more
DesktopLyrics 2.6.6 - Displays current i...
DesktopLyrics is an application that displays the lyrics of the song currently playing in "iTunes" right on your desktop. The lyrics for the song have to be set in iTunes; DesktopLyrics does nothing... Read more
VOX 2.5.1 - Music player that supports m...
VOX is a beautiful music player that supports many filetypes. The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all... Read more
NetNewsWire 4.0.0 - RSS and Atom news re...
NetNewsWire is the best way to keep up with the sites and authors you read most regularly. Let NetNewsWire pull down the latest articles, and read them in a distraction-free and Mac-like way. Native... Read more
MacUpdate Desktop 6.0.6 - Search and ins...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
ForkLift 2.6.5 - Powerful file manager:...
ForkLift is a powerful file manager and ferociously fast FTP client clothed in a clean and versatile UI that offers the combination of absolute simplicity and raw power expected from a well-executed... Read more
Drive Genius 4.1.0 - Powerful system uti...
Drive Genius 4 gives you faster performance from your Mac while also protecting it. The award-winning and improved DrivePulse feature alerts you to hard drive issues before they become major problems... Read more

Biz Builder Delux (Games)
Biz Builder Delux 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Ah, there's nothing like the rhythmic bustle of a burgeoning business burg... especially when you're the one building it... | Read more »
Auroch Digital is Bringing Back Games Wo...
| Read more »
Carbo - Handwriting in the Digital Age...
Carbo - Handwriting in the Digital Age 1.0 Device: iOS Universal Category: Productivity Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Draggy Dead (Games)
Draggy Dead 1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1 (iTunes) Description: Ditch your dead end job and take up a rewarding career in Grave Robbing today!Guide the recently deceased to a fun filled life of... | Read more »
Bad Dinos (Games)
Bad Dinos 1.0.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.0 (iTunes) Description: | Read more »
The Apple Watch isn't Great as a Fi...
| Read more »
Show the World What You See With Stre.am...
Live broadcasting is getting popular on mobile devices, which is why you can now get Stre.am, by Infinite Takes. [Read more] | Read more »
PhotoTime's 2.1 Update Adds Apple W...
The latest PhotoTime update is adding even more functionality to the handy photo organizing app. Yep, including Apple Watch support. [Read more] | Read more »
Oh My Glob! Adventure Time Puzzle Quest...
Finn and Jake are taking over D3 Go!'s popular puzzle game series in the upcoming Adventure Time Puzzle Quest. [Read more] | Read more »
Earthcore: Shattered Elements - Tips, Tr...
At first glance, Earthcore: Shattered Elements seems like a rather simple card-battling game. Once you’re introduced to skills that will change quite a bit. Even more so once you start to acquire hero cards. But it’s not so complicated that we... | Read more »

Price Scanner via MacPrices.net

OtterBox Maximizes Portability, Productivity...
From the kitchen recipe book to the boarsroom presentation, the OtterBox Agility Tablet System turns tablets into one of the most versatile pieces of handheld technology available. Available now, the... Read more
Launch of New Car App Gallery and Open Develo...
Automatic, a company on a mission to bring the power of the Internet into every car, has announced the launch of the Automatic App Gallery, an app store for nearly every car or truck on the road... Read more
Memorial Day Weekend Sale: 13-inch 1.6GHz Mac...
Best Buy has the new 13″ 1.6GHz/128GB MacBook Air on sale for $849 on their online store this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders... Read more
Memorial Day Weekend Sale: 27-inch 3.5GHz 5K...
Best Buy has the 27″ 3.5GHz 5K iMac on sale for $2099.99 this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders only, in-store prices may vary.... Read more
Sale! 16GB iPad mini 3 for $349, save $50
B&H Photo has the 16GB iPad mini 3 WiFi on sale for $349 including free shipping plus NY sales tax only. Their price is $50 off MSRP, and it’s the lowest price available for this model. Read more
Price drop on 2014 15-inch Retina MacBook Pro...
B&H Photo has dropped prices on 2014 15″ Retina MacBook Pros by $200. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799.99 save $200 - 15″ 2.5GHz... Read more
With a Mission to Make Mobile Free, Scratch W...
Scratch Wireless, claiming to be the world’s first truly free mobile service, has announced the availability of a new Scratch-enabled Android smartphone, the Coolpad Arise. The smartphone is equipped... Read more
First-Ever Titanium Alloy Curved iPhone 6 Scr...
One of the most common problems with mobile phones is damage to the screens. The slightest drop can cause a dreaded spider web of gashes and cracks in the glass panel surface that can cost $hundreds... Read more
Preorder new 12-inch MacBook, $10 off, save o...
Adorama has new 12″ Retina MacBooks available for preorder for $10 off MSRP including free shipping plus NY & NJ sales tax only. For a limited time, Adorama will include a free Apple USB-C to USB... Read more
Will iOS 9 Finally Bring Productivity Friendl...
Ah, the irony. From its original announcement in 2010, Apple has doggedly insisted that the iPad remain “simple,” thus arbitrarily limiting its considerable potential as a content creation and... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Business Development Manager - *Apple* Pay...
**Job Summary** Apple Pay is seeking an experienced Business Development professional to join the Apple Pay team to develop partnerships and strategic alliances with Read more
Project Manager, *Apple* Retail New Store O...
**Job Summary** An Apple Retail New Store Openings & Remodels Project Manager is responsible for successfully managing the openings, remodels, and small works of Read more
SW QA Engineer - *Apple* TV - Apple (United...
**Job Summary** The Apple TV team is looking for experienced Quality Assurance Engineers with a passion for delivering first in class home entertainment solutions. **Key Read more
Partner Marketing Manager - *Apple* Pay - A...
**Job Summary** The Apple Pay partner marketing team is looking for a marketing manager to develop and drive US marketing programs with our financial institution Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.