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- |

 
AAPL
$99.02
Apple Inc.
+1.35
MSFT
$43.97
Microsoft Corpora
-0.53
GOOG
$590.60
Google Inc.
+1.58

MacTech Search:
Community Search:

Software Updates via MacUpdate

Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more
TotalFinder 1.6.2 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more
Vienna 3.0.0 RC 2 :be5265e: - RSS and At...
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
VLC Media Player 2.1.5 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Default Folder X 4.6.7 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more
TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more
Autopano Giga 3.6 - Stitch multiple imag...
Autopano Giga allows you to stitch 2, 20, or 2,000 images. Version 3.0 integrates impressive new features that will definitely make you adopt Autopano Pro or Autopano Giga: Choose between 9... Read more

Latest Forum Discussions

See All

Traps n’ Gemstones Review
Traps n’ Gemstones Review By Campbell Bird on July 28th, 2014 Our Rating: :: CASTLEVANIA JONESUniversal App - Designed for iPhone and iPad Fight mummies, dig tunnels, and ride a runaway minecart to discover ancient secrets in this... | Read more »
The Phantom PI Mission Apparition Review
The Phantom PI Mission Apparition Review By Jordan Minor on July 28th, 2014 Our Rating: :: GHOSTS BUSTEDUniversal App - Designed for iPhone and iPad The Phantom PI is an exceedingly clever and well-crafted adventure game.   | Read more »
More Stubies Are Coming Your Way in a Ne...
More Stubies Are Coming Your Way in a New Update Posted by Jessica Fisher on July 28th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
The Great Prank War Review
The Great Prank War Review By Nadia Oxford on July 28th, 2014 Our Rating: :: PRANKING IS SERIOUS BUSINESSUniversal App - Designed for iPhone and iPad Though short, The Great Prank War offers an interesting and fun mix of action and... | Read more »
Marvel Contest of Champions Announced at...
Marvel Contest of Champions Announced at Comic-Con Posted by Jennifer Allen on July 28th, 2014 [ permalink ] Announced over the weekend at San Diego Comic-Con was the fairly exciting looking Marvel Contest of Champions. | Read more »
Teenage Mutant Ninja Turtles Review
Teenage Mutant Ninja Turtles Review By Jennifer Allen on July 28th, 2014 Our Rating: :: DULL SWIPINGUniversal App - Designed for iPhone and iPad The pizza power is weak when it comes to this Teenage Mutant Ninja Turtles game.   | Read more »
Exploration Focused Puzzle Game Beatbudd...
Exploration Focused Puzzle Game Beatbuddy Set to Make Transition from PC to iOS this September Posted by Jennifer Allen on July 28th, 2014 [ permalink ] | Read more »
PlanetHD
PlanetHD By Nadia Oxford on July 28th, 2014 Our Rating: :: SPACE MADNESSUniversal App - Designed for iPhone and iPad PlanetHD will keep players busy for a while, though its unpredictable physics are a handful to deal with.   | Read more »
This Week at 148Apps: July 21-25, 2014
Another Week of Expert App Reviews   At 148Apps, we help you sort through the great ocean of apps to find the ones we think you’ll like and the ones you’ll need. Our top picks become Editor’s Choice, our stamp of approval for apps with that little... | Read more »
Reddme for iPhone - The Reddit Client (...
Reddme for iPhone - The Reddit Client 1.0 Device: iOS iPhone Category: News Price: $.99, Version: 1.0 (iTunes) Description: Reddme for iPhone is an iOS 7-optimized Reddit client that offers a refreshing new way to experience Reddit... | Read more »

Price Scanner via MacPrices.net

13-inch 2.5GHz MacBook Pro on sale for $1099,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $1099.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Roundup of Apple refurbished MacBook Pros, th...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available for up to $400 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. Their prices... Read more
Record Mac Shipments In Q2/14 Confound Analys...
A Seeking Alpha Trefis commentary notes that Apple’s fiscal Q3 2014 results released July 22, beat market predictions on earnings, although revenues were slightly lower than anticipated. Apple’s Mac’... Read more
Intel To Launch Core M Silicon For Use In Not...
Digitimes’ Monica Chen and Joseph Tsai, report that Intel will launch 14nm-based Core M series processors specifically for use in fanless notebook/tablet 2-in-1 models in Q4 2014, with many models to... Read more
Apple’s 2014 Back to School promotion: $100 g...
 Apple’s 2014 Back to School promotion includes a free $100 App Store Gift Card with the purchase of any new Mac (Mac mini excluded), or a $50 Gift Card with the purchase of an iPad or iPhone,... Read more
iMacs on sale for $150 off MSRP, $250 off for...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
Mac minis on sale for $100 off MSRP, starting...
Best Buy has Mac minis on sale for $100 off MSRP. Choose free shipping or free instant local store pickup. Prices are for online orders only, in-store prices may vary: 2.5GHz Mac mini: $499.99 2.3GHz... Read more
Global Tablet Market Grows 11% in Q2/14 Notwi...
Worldwide tablet sales grew 11.0 percent year over year in the second quarter of 2014, with shipments reaching 49.3 million units according to preliminary data from the International Data Corporation... Read more
New iPhone 6 Models to Have Staggered Release...
Digitimes’ Cage Chao and Steve Shen report that according to unnamed sources in Apple’s upstream iPhone supply chain, the new 5.5-inch iPhone will be released several months later than the new 4.7-... Read more
New iOS App Helps People Feel Good About thei...
Mobile shoppers looking for big savings at their favorite stores can turn to the Goodshop app, a new iOS app with the latest coupons and deals at more than 5,000 online stores. In addition to being a... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
WW Sales Program Manager, *Apple* Online St...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.