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

1Password 6.6.4 - Powerful password mana...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
Cocktail 10.3.1 - General maintenance an...
Cocktail is a general purpose utility for macOS that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Safari Technology Preview 10.2 - The new...
Safari Technology Preview contains the most recent additions and improvements to WebKit and the latest advances in Safari web technologies. And once installed, you will receive notifications of... Read more
Together 3.8 - Store and organize all of...
Together helps you organize your Mac, giving you the ability to store, edit and preview your files in a single clean, uncluttered interface. Features Smart storage. With simple drag-and-drop... Read more
GraphicConverter 10.4 - $39.95
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
beaTunes 4.6.13 - Organize your music co...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
Vienna 3.1.9 :e81515b: - RSS and Atom ne...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more
iExplorer 4.0.12.0 - View and transfer f...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
OpenEmu 2.0.5 - Open Source game-emulati...
OpenEmu is about to change the world of video game emulation, one console at a time... For the first time, the 'It just works' philosophy now extends to open source video game emulation on the Mac.... Read more
TextSoap 8.3.3 - Automate tedious text d...
TextSoap can automatically remove unwanted characters, fix up messed up carriage returns, and do pretty much anything else that we can think of to text. Save time and effort. Be more productive. Stop... Read more

Leap to victory in Nexx Studios new plat...
You’re always a hop, skip, and a jump away from a fiery death in Temple Jump, a new platformer-cum-endless runner from Nexx Studio. It’s out now on both iOS and Android if you’re an adventurer seeking treasure in a crumbling, pixel-laden temple. | Read more »
Failbetter Games details changes coming...
Sunless Sea, Failbetter Games' dark and gloomy sea explorer, sets sail for the iPad tomorrow. Ahead of the game's launch, Failbetter took to Twitter to discuss what will be different in the mobile version of the game. Many of the changes make... | Read more »
Splish, splash! The Pokémon GO Water Fes...
Niantic is back with a new festival for dedicated Pokémon GO collectors. The Water Festival officially kicks off today at 1 P.M. PDT and runs through March 29. Magikarp, Squirtle, Totodile, and their assorted evolved forms will be appearing at... | Read more »
Death Road to Canada (Games)
Death Road to Canada 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: Get it now at the low launch price! Price will go up a dollar every major update. Update news at the bottom of this... | Read more »
Bean's Quest Beginner's Guide:...
Bean's Quest is a new take on both the classic platformer and the endless runner, and it's free on the App Store for the time being. Instead of running constantly, you can't stop jumping. That adds a surprising new level of challenge to the game... | Read more »
How to rake in the cash in Bit City
Our last Bit City guide covered the basics. Now it's time to get into some of the more advanced techniques. In the later cities, cash flow becomes much more difficult, so you'll want to develop some strategies if you want to complete each level.... | Read more »
PixelTerra (Games)
PixelTerra 1.1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1.1 (iTunes) Description: The world of PixelTerra is quite dangerous so you need to build a shelter, find some food supply and get ready to protect... | Read more »
Tokaido™ (Games)
Tokaido™ 1.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.0 (iTunes) Description: Discover the digital adaptation of Tokaido, the boardgame phenomenon that has already sold more than 250,000 copies worldwide, and... | Read more »
Card Thief (Games)
Card Thief 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Card Thief is a solitaire style stealth game played with a deck of cards. In Card Thief you move through a deck of cards as a... | Read more »
Smilegate’s crafting battler Super Tank...
Super Tank Rumbleputs you in the seat of your very own, handcrafted tank. You can choose from over 100 different parts to create your Super Tank before taking it out to wreak havoc on your opponents in glorious PVP combat. Now, Smilegate is upping... | Read more »

Price Scanner via MacPrices.net

Apple’s iPhone 6s Tops Best-Selling Smartphon...
In terms of shipments, the iPhone 6s from Apple bested all competitors for sales in 2016, according to new analysis from IHS Markit, a world leader in critical information, analytics and solutions.... Read more
Logitech Rugged Combo Protective iPad Case an...
Logitech has announced its Logitech Rugged Combo, Logitech Rugged Case, and Logitech Add-on Keyboard for Rugged Case for Apple’s new, more affordable $329 9.7-inch iPad, a complete solution designed... Read more
T-Mobile To Offer iPhone 7 and iPhone 7 Plus...
T-Mobile has announced it will offer iPhone 7 and iPhone 7 Plus (PRODUCT)RED Special Edition in a vibrant red aluminum finish. The introduction of this special edition iPhone celebrates Apple’s 10... Read more
9-inch 128GB iPad Pros on sale for $50-$70 of...
B&H Photo has 9.7″ 128GB Apple WiFi iPad Pros on sale for up to $70 off MSRP, each including free shipping. B&H charges sales tax in NY only: - 9″ Space Gray 128GB WiFi iPad Pro: $649 $50... Read more
27-inch iMacs on sale for up to $200 off MSRP...
B&H Photo has 27″ Apple iMacs on sale for up to $200 off MSRP, each including free shipping plus NY sales tax only: - 27″ 3.3GHz iMac 5K: $2099 $200 off MSRP - 27″ 3.2GHz/1TB Fusion iMac 5K: $... Read more
Save up to $600 with Apple refurbished Mac Pr...
Apple has Certified Refurbished Mac Pros available for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The following... Read more
Save $230 with Apple Certified Refurbished 13...
Apple is now offering Certified Refurbished 2016 13″ 2.0GHz non-Touch Bar MacBook Pros for $230 off original MSRP. An Apple one-year warranty is included with each model, and shipping is free: - 13″... Read more
Apple price trackers, updated continuously
Scan our Apple Price Trackers for the latest information on sales, bundles, and availability on systems from Apple’s authorized internet/catalog resellers. We update the trackers continuously: - 15″... Read more
13-inch Touch Bar MacBook Pros on sale for up...
B&H Photo has the Apple 13″ Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.9GHz/512GB Touch Bar... Read more
Today only! 15-inch 2.7GHz Space Gray Touch B...
B&H Photo has the new 2016 15″ 2.7GHz Space Gray Apple Touch Bar MacBook Pro in stock today and on sale for $300 off MSRP for today only. Shipping is free, and B&H charges NY sales tax only... Read more

Jobs Board

*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Director, *Apple* Program - ERP & Cloud...
Leading Pharmaceutical / Biotech Company is announcing a Director, Apple Program - ERP & Cloud Platform Architecture Lead opportunity in Northbrook, IL. Purpose & Read more
Fulltime aan de slag als shopmanager in een h...
Ben jij helemaal gek van Apple -producten en vind je het helemaal super om fulltime shopmanager te zijn in een jonge en hippe elektronicazaak? Wil jij werken in Read more
Starte Dein Karriere-Abenteuer in den Hauptst...
…mehrsprachigen Teams betreust Du Kunden von bekannten globale Marken wie Apple , Mercedes, Facebook, Expedia, und vielen anderen! Funktion Du wolltest schon Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.