1 /******************************************************************************
2 *
3 * Project: OpenCPN
4 * Purpose: Extern C Linked Utilities
5 * Author: David Register
6 *
7 ***************************************************************************
8 * Copyright (C) 2010 by David S. Register *
9 * *
10 * This program is free software; you can redistribute it and/or modify *
11 * it under the terms of the GNU General Public License as published by *
12 * the Free Software Foundation; either version 2 of the License, or *
13 * (at your option) any later version. *
14 * *
15 * This program is distributed in the hope that it will be useful, *
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
18 * GNU General Public License for more details. *
19 * *
20 * You should have received a copy of the GNU General Public License *
21 * along with this program; if not, write to the *
22 * Free Software Foundation, Inc., *
23 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *
24 ***************************************************************************
25 *
26 */
27 #include <stdio.h>
28 #include <stdarg.h>
29 #include <string.h>
30 #include <math.h>
31 #include <ctype.h>
32
33 #include "cutil.h"
34 #include "vector2D.h"
35
36
37 int Intersect(MyPoint, MyPoint, MyPoint, MyPoint) ;
38 int CCW(MyPoint, MyPoint, MyPoint) ;
39
40 int Intersect_FL(float_2Dpt, float_2Dpt, float_2Dpt, float_2Dpt) ;
41 int CCW_FL(float_2Dpt, float_2Dpt, float_2Dpt) ;
42
43
44 /*************************************************************************
45
46
47 * FUNCTION: G_PtInPolygon
48 *
49 * PURPOSE
50 * This routine determines if the point passed is in the polygon. It uses
51 * the classical polygon hit-testing algorithm: a horizontal ray starting
52 * at the point is extended infinitely rightwards and the number of
53 * polygon edges that intersect the ray are counted. If the number is odd,
54 * the point is inside the polygon.
55 *
56 * Polygon is assumed OPEN, not CLOSED.
57 * RETURN VALUE
58 * (bool) TRUE if the point is inside the polygon, FALSE if not.
59 *************************************************************************/
60
61
G_PtInPolygon(MyPoint * rgpts,int wnumpts,float x,float y)62 int G_PtInPolygon(MyPoint *rgpts, int wnumpts, float x, float y)
63 {
64
65 MyPoint *ppt, *ppt1 ;
66 int i ;
67 MyPoint pt1, pt2, pt0 ;
68 int wnumintsct = 0 ;
69
70
71 pt0.x = x;
72 pt0.y = y;
73
74 pt1 = pt2 = pt0 ;
75 pt2.x = 1.e8;
76
77 // Now go through each of the lines in the polygon and see if it
78 // intersects
79 for (i = 0, ppt = rgpts ; i < wnumpts-1 ; i++, ppt++)
80 {
81 ppt1 = ppt;
82 ppt1++;
83 if (Intersect(pt0, pt2, *ppt, *(ppt1)))
84 wnumintsct++ ;
85 }
86
87 // And the last line
88 if (Intersect(pt0, pt2, *ppt, *rgpts))
89 wnumintsct++ ;
90
91 return (wnumintsct&1) ;
92
93 }
94
95
96 /*************************************************************************
97
98 0
99 * FUNCTION: Intersect
100 *
101 * PURPOSE
102 * Given two line segments, determine if they intersect.
103 *
104 * RETURN VALUE
105 * TRUE if they intersect, FALSE if not.
106 *************************************************************************/
107
108
Intersect(MyPoint p1,MyPoint p2,MyPoint p3,MyPoint p4)109 int Intersect(MyPoint p1, MyPoint p2, MyPoint p3, MyPoint p4) {
110 int i;
111 i = CCW(p1, p2, p3);
112 i = CCW(p1, p2, p4);
113 i = CCW(p3, p4, p1);
114 i = CCW(p3, p4, p2);
115 return ((( CCW(p1, p2, p3) * CCW(p1, p2, p4)) <= 0)
116 && (( CCW(p3, p4, p1) * CCW(p3, p4, p2) <= 0) )) ;
117
118 }
119 /*************************************************************************
120
121
122 * FUNCTION: CCW (CounterClockWise)
123 *
124 * PURPOSE
125 * Determines, given three points, if when travelling from the first to
126 * the second to the third, we travel in a counterclockwise direction.
127 *
128 * RETURN VALUE
129 * (int) 1 if the movement is in a counterclockwise direction, -1 if
130 * not.
131 *************************************************************************/
132
133
CCW(MyPoint p0,MyPoint p1,MyPoint p2)134 int CCW(MyPoint p0, MyPoint p1, MyPoint p2) {
135 double dx1, dx2 ;
136 double dy1, dy2 ;
137
138 dx1 = p1.x - p0.x ; dx2 = p2.x - p0.x ;
139 dy1 = p1.y - p0.y ; dy2 = p2.y - p0.y ;
140
141 /* This is a slope comparison: we don't do divisions because
142 * of divide by zero possibilities with pure horizontal and pure
143 * vertical lines.
144 */
145 return ((dx1 * dy2 > dy1 * dx2) ? 1 : -1) ;
146
147 }
148
149
G_PtInPolygon_FL(float_2Dpt * rgpts,int wnumpts,float x,float y)150 int G_PtInPolygon_FL(float_2Dpt *rgpts, int wnumpts, float x, float y)
151 {
152
153 float_2Dpt *ppt, *ppt1 ;
154 int i ;
155 float_2Dpt pt1, pt2, pt0 ;
156 int wnumintsct = 0 ;
157
158
159 pt0.x = x;
160 pt0.y = y;
161
162 pt1 = pt2 = pt0 ;
163 pt2.x = 1.e8;
164
165 // Now go through each of the lines in the polygon and see if it
166 // intersects
167 for (i = 0, ppt = rgpts ; i < wnumpts-1 ; i++, ppt++)
168 {
169 ppt1 = ppt;
170 ppt1++;
171 if (Intersect_FL(pt0, pt2, *ppt, *(ppt1)))
172 wnumintsct++ ;
173 }
174
175 // And the last line
176 if (Intersect_FL(pt0, pt2, *ppt, *rgpts))
177 wnumintsct++ ;
178
179 return (wnumintsct&1) ;
180
181 }
182
183
184 /*************************************************************************
185
186 * FUNCTION: Intersect_FL
187 *
188 * PURPOSE
189 * Given two line segments, determine if they intersect.
190 *
191 * RETURN VALUE
192 * TRUE if they intersect, FALSE if not.
193 *************************************************************************/
194
195
Intersect_FL(float_2Dpt p1,float_2Dpt p2,float_2Dpt p3,float_2Dpt p4)196 int Intersect_FL(float_2Dpt p1, float_2Dpt p2, float_2Dpt p3, float_2Dpt p4) {
197 int i;
198 i = CCW_FL(p1, p2, p3);
199 i = CCW_FL(p1, p2, p4);
200 i = CCW_FL(p3, p4, p1);
201 i = CCW_FL(p3, p4, p2);
202 return ((( CCW_FL(p1, p2, p3) * CCW_FL(p1, p2, p4)) <= 0)
203 && (( CCW_FL(p3, p4, p1) * CCW_FL(p3, p4, p2) <= 0) )) ;
204
205 }
206 /*************************************************************************
207
208
209 * FUNCTION: CCW_FL (CounterClockWise)
210 *
211 * PURPOSE
212 * Determines, given three points, if when travelling from the first to
213 * the second to the third, we travel in a counterclockwise direction.
214 *
215 * RETURN VALUE
216 * (int) 1 if the movement is in a counterclockwise direction, -1 if
217 * not.
218 *************************************************************************/
219
220
CCW_FL(float_2Dpt p0,float_2Dpt p1,float_2Dpt p2)221 int CCW_FL(float_2Dpt p0, float_2Dpt p1, float_2Dpt p2) {
222 double dx1, dx2 ;
223 double dy1, dy2 ;
224
225 dx1 = p1.x - p0.x ; dx2 = p2.x - p0.x ;
226 dy1 = p1.y - p0.y ; dy2 = p2.y - p0.y ;
227
228 /* This is a slope comparison: we don't do divisions because
229 * of divide by zero possibilities with pure horizontal and pure
230 * vertical lines.
231 */
232 return ((dx1 * dy2 > dy1 * dx2) ? 1 : -1) ;
233
234 }
235
236
237
238
239 #define CTRUE -1
240 #define CFALSE 0
241
242 typedef enum {
243 LEFT, RIGHT, BOTTOM, TOP
244 } edge;
245 typedef long outcode;
246
247
248 /* Local variables for cohen_sutherland_line_clip: */
249 struct LOC_cohen_sutherland_line_clip {
250 double xmin, xmax, ymin, ymax;
251 } ;
252
CompOutCode(double x,double y,outcode * code,struct LOC_cohen_sutherland_line_clip * LINK)253 void CompOutCode (double x, double y, outcode *code, struct LOC_cohen_sutherland_line_clip *LINK)
254 {
255 /*Compute outcode for the point (x,y) */
256 *code = 0;
257 if (y > LINK->ymax)
258 *code = 1L << ((long)TOP);
259 else if (y < LINK->ymin)
260 *code = 1L << ((long)BOTTOM);
261 if (x > LINK->xmax)
262 *code |= 1L << ((long)RIGHT);
263 else if (x < LINK->xmin)
264 *code |= 1L << ((long)LEFT);
265 }
266
267
cohen_sutherland_line_clip_d(double * x0,double * y0,double * x1,double * y1,double xmin_,double xmax_,double ymin_,double ymax_)268 ClipResult cohen_sutherland_line_clip_d (double *x0, double *y0, double *x1, double *y1,
269 double xmin_, double xmax_, double ymin_, double ymax_)
270 {
271 /* Cohen-Sutherland clipping algorithm for line P0=(x1,y0) to P1=(x1,y1)
272 and clip rectangle with diagonal from (xmin,ymin) to (xmax,ymax).*/
273 struct LOC_cohen_sutherland_line_clip V;
274 int done = CFALSE;
275 ClipResult clip = Visible;
276 outcode outcode0, outcode1, outcodeOut;
277 /*Outcodes for P0,P1, and whichever point lies outside the clip rectangle*/
278 double x=0., y=0.;
279
280 V.xmin = xmin_;
281 V.xmax = xmax_;
282 V.ymin = ymin_;
283 V.ymax = ymax_;
284 CompOutCode(*x0, *y0, &outcode0, &V);
285 CompOutCode(*x1, *y1, &outcode1, &V);
286 do {
287 if (outcode0 == 0 && outcode1 == 0) { /*Trivial accept and exit*/
288 done = CTRUE;
289 } else if ((outcode0 & outcode1) != 0) {
290 clip = Invisible;
291 done = CTRUE;
292 }
293 /*Logical intersection is true, so trivial reject and exit.*/
294 else {
295 clip = Visible;
296 /*Failed both tests, so calculate the line segment to clip;
297 from an outside point to an intersection with clip edge.*/
298 /*At least one endpoint is outside the clip rectangle; pick it.*/
299 if (outcode0 != 0)
300 outcodeOut = outcode0;
301 else
302 outcodeOut = outcode1;
303 /*Now find intersection point;
304 use formulas y=y0+slope*(x-x0),x=x0+(1/slope)*(y-y0).*/
305
306 if (((1L << ((long)TOP)) & outcodeOut) != 0) {
307 /*Divide line at top of clip rectangle*/
308 x = *x0 + (*x1 - *x0) * (V.ymax - *y0) / (*y1 - *y0);
309 y = V.ymax;
310 } else if (((1L << ((long)BOTTOM)) & outcodeOut) != 0) {
311 /*Divide line at bottom of clip rectangle*/
312 x = *x0 + (*x1 - *x0) * (V.ymin - *y0) / (*y1 - *y0);
313 y = V.ymin;
314 } else if (((1L << ((long)RIGHT)) & outcodeOut) != 0) {
315 /*Divide line at right edge of clip rectangle*/
316 y = *y0 + (*y1 - *y0) * (V.xmax - *x0) / (*x1 - *x0);
317 x = V.xmax;
318 } else if (((1L << ((long)LEFT)) & outcodeOut) != 0) {
319 /*Divide line at left edge of clip rectangle*/
320 y = *y0 + (*y1 - *y0) * (V.xmin - *x0) / (*x1 - *x0);
321 x = V.xmin;
322 }
323 /*Now we move outside point to intersection point to clip,
324 and get ready for next pass.*/
325 if (outcodeOut == outcode0) {
326 *x0 = x;
327 *y0 = y;
328 CompOutCode(*x0, *y0, &outcode0, &V);
329 } else {
330 *x1 = x;
331 *y1 = y;
332 CompOutCode(*x1, *y1, &outcode1, &V);
333 }
334 }
335 } while (!done);
336 return clip;
337 }
338
cohen_sutherland_line_clip_i(int * x0_,int * y0_,int * x1_,int * y1_,int xmin_,int xmax_,int ymin_,int ymax_)339 ClipResult cohen_sutherland_line_clip_i (int *x0_, int *y0_, int *x1_, int *y1_,
340 int xmin_, int xmax_, int ymin_, int ymax_)
341 {
342 ClipResult ret;
343 double x0,y0,x1,y1;
344 x0 = *x0_;
345 y0 = *y0_;
346 x1 = *x1_;
347 y1 = *y1_;
348 ret = cohen_sutherland_line_clip_d (&x0, &y0, &x1, &y1,
349 (double)xmin_, (double)xmax_,
350 (double)ymin_, (double)ymax_);
351 *x0_ = (int)x0;
352 *y0_ = (int)y0;
353 *x1_ = (int)x1;
354 *y1_ = (int)y1;
355 return ret;
356 }
357
358
round_msvc(double x)359 double round_msvc (double x)
360 {
361 return(floor(x + 0.5));
362
363 }
364
365 #ifdef __MSVC__
366 #include <windows.h>
367 #include <float.h> // for _clear87()
368
MyUnhandledExceptionFilter(struct _EXCEPTION_POINTERS * ExceptionInfo)369 extern long __stdcall MyUnhandledExceptionFilter( struct _EXCEPTION_POINTERS *ExceptionInfo )
370 {
371 // return EXCEPTION_EXECUTE_HANDLER ; // terminates the app
372
373 switch(ExceptionInfo->ExceptionRecord->ExceptionCode)
374 {
375 case EXCEPTION_FLT_DENORMAL_OPERAND:
376 case EXCEPTION_FLT_DIVIDE_BY_ZERO:
377 case EXCEPTION_FLT_INEXACT_RESULT:
378 case EXCEPTION_FLT_INVALID_OPERATION:
379 case EXCEPTION_FLT_OVERFLOW:
380 case EXCEPTION_FLT_STACK_CHECK:
381 case EXCEPTION_FLT_UNDERFLOW:
382 _clear87();
383 return EXCEPTION_CONTINUE_EXECUTION ; // retry
384
385 default:
386 return EXCEPTION_CONTINUE_SEARCH ; // standard fatal dialog box
387 }
388 }
389
390 #endif
391
392 /* Replacement for __MSVC__ in absence of snprintf or _snprintf */
393 #ifdef __MSVC__
mysnprintf(char * buffer,int count,const char * format,...)394 extern int mysnprintf( char *buffer, int count, const char *format, ... )
395 {
396 int ret;
397
398 va_list arg;
399 va_start(arg, format);
400 ret = _vsnprintf(buffer, count, format, arg);
401
402 va_end(arg);
403 return ret;
404 }
405 #endif
406
oldNextPow2(int size)407 int oldNextPow2(int size)
408 {
409 /* compute dimensions needed as next larger power of 2 */
410 int a = size;
411 int p = 0;
412 while( a ) {
413 a = a >> 1;
414 p++;
415 }
416 return 1 << p;
417 }
418
NextPow2(int size)419 int NextPow2(int size)
420 {
421 int n = size-1; // compute dimensions needed as next larger power of 2
422 int shift = 1;
423 while ((n+1) & n){
424 n |= n >> shift;
425 shift <<= 1;
426 }
427
428 return n + 1;
429 }
430
DouglasPeucker(double * PointList,int fp,int lp,double epsilon,std::vector<int> * keep)431 void DouglasPeucker(double *PointList, int fp, int lp, double epsilon, std::vector<int> *keep)
432 {
433 // Find the point with the maximum distance
434 double dmax = 0;
435 int index = 0;
436
437 vector2D va(PointList[2*fp] - PointList[2*lp],
438 PointList[2*fp+1] - PointList[2*lp+1]);
439
440 double da = va.x*va.x + va.y*va.y;
441 for(int i = fp+1 ; i < lp ; ++i) {
442 vector2D vb(PointList[2*i] - PointList[2*fp],
443 PointList[2*i + 1] - PointList[2*fp+1]);
444
445 double dab = va.x*vb.x + va.y*vb.y;
446 double db = vb.x*vb.x + vb.y*vb.y;
447 double d = da - dab*dab/db;
448 if ( d > dmax ) {
449 index = i;
450 dmax = d;
451 }
452 }
453 // If max distance is greater than epsilon, recursively simplify
454 if ( dmax > epsilon*epsilon ) {
455 keep->push_back(index);
456
457 // Recursive call
458 DouglasPeucker(PointList, fp, index, epsilon, keep);
459 DouglasPeucker(PointList, index, lp, epsilon, keep);
460
461 }
462 }
463
DouglasPeuckerF(float * PointList,int fp,int lp,double epsilon,std::vector<int> * keep)464 void DouglasPeuckerF(float *PointList, int fp, int lp, double epsilon, std::vector<int> *keep)
465 {
466 // Find the point with the maximum distance
467 double dmax = 0;
468 int index = 0;
469
470 vector2D va(PointList[2*fp] - PointList[2*lp],
471 PointList[2*fp+1] - PointList[2*lp+1]);
472
473 double da = va.x*va.x + va.y*va.y;
474 for(int i = fp+1 ; i < lp ; ++i) {
475 vector2D vb(PointList[2*i] - PointList[2*fp],
476 PointList[2*i + 1] - PointList[2*fp+1]);
477
478 double dab = va.x*vb.x + va.y*vb.y;
479 double db = vb.x*vb.x + vb.y*vb.y;
480 double d = da - dab*dab/db;
481 if ( d > dmax ) {
482 index = i;
483 dmax = d;
484 }
485 }
486 // If max distance is greater than epsilon, recursively simplify
487 if ( dmax > epsilon*epsilon ) {
488 keep->push_back(index);
489
490 // Recursive call
491 DouglasPeuckerF(PointList, fp, index, epsilon, keep);
492 DouglasPeuckerF(PointList, index, lp, epsilon, keep);
493
494 }
495 }
496
DouglasPeuckerFI(float * PointList,int fp,int lp,double epsilon,std::vector<bool> & keep)497 void DouglasPeuckerFI(float *PointList, int fp, int lp, double epsilon, std::vector<bool> &keep)
498 {
499 keep[fp] = true;
500 keep[lp] = true;
501
502 // Find the point with the maximum distance
503 double dmax = 0;
504 int maxdistIndex = -1;
505
506 vector2D va(PointList[2*fp] - PointList[2*lp],
507 PointList[2*fp+1] - PointList[2*lp+1]);
508
509 double da = va.x*va.x + va.y*va.y;
510 for(int i = fp+1 ; i < lp ; ++i) {
511 vector2D vb(PointList[2*i] - PointList[2*fp],
512 PointList[2*i + 1] - PointList[2*fp+1]);
513
514 double dab = va.x*vb.x + va.y*vb.y;
515 double db = vb.x*vb.x + vb.y*vb.y;
516 double d = da - dab*dab/db;
517 if ( d > dmax ) {
518 maxdistIndex = i;
519 dmax = d;
520 }
521 }
522 // If max distance is greater than epsilon, recursively simplify
523 if ( dmax > epsilon*epsilon ) {
524
525 // Recursive call
526 DouglasPeuckerFI(PointList, fp, maxdistIndex, epsilon, keep);
527 DouglasPeuckerFI(PointList, maxdistIndex, lp, epsilon, keep);
528
529 }
530 }
531
DouglasPeuckerDI(double * PointList,int fp,int lp,double epsilon,std::vector<bool> & keep)532 void DouglasPeuckerDI(double *PointList, int fp, int lp, double epsilon, std::vector<bool> &keep)
533 {
534 keep[fp] = true;
535 keep[lp] = true;
536
537 // Find the point with the maximum distance
538 double dmax = 0;
539 int maxdistIndex = -1;
540
541 vector2D va(PointList[3*fp] - PointList[3*lp],
542 PointList[3*fp+1] - PointList[3*lp+1]);
543 double da = sqrt(va.x*va.x + va.y*va.y);
544
545 double y2 = PointList[3*lp+1];
546 double y1 = PointList[3*fp+1];
547 double x2 = PointList[3*lp];
548 double x1 = PointList[3*fp];
549
550 for(int i = fp+1 ; i < lp ; ++i) {
551
552 // Distance from point to line.
553 // ref. https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
554 double d = (y2 - y1) * PointList[3 * i] -
555 (x2 - x1) * PointList[3 * i + 1] +
556 (x2 * y1) - (y2 * x1);
557
558 d = fabs( d / da);
559
560 if ( d > dmax ) {
561 maxdistIndex = i;
562 dmax = d;
563 }
564 }
565 // If max distance is greater than epsilon, recursively simplify
566 if ( dmax > epsilon ) {
567
568 // Recursive call
569 DouglasPeuckerDI(PointList, fp, maxdistIndex, epsilon, keep);
570 DouglasPeuckerDI(PointList, maxdistIndex, lp, epsilon, keep);
571
572 }
573 }
574
DouglasPeuckerM(double * PointList,int fp,int lp,double epsilon,std::vector<int> * keep)575 void DouglasPeuckerM(double *PointList, int fp, int lp, double epsilon, std::vector<int> *keep)
576 {
577 // Find the point with the maximum distance
578 int index = 0;
579 double lmax = 0;
580
581 vector2D va(PointList[2*fp] - PointList[2*lp],
582 PointList[2*fp+1] - PointList[2*lp+1]);
583
584 for(int i = fp+1 ; i < lp ; ++i) {
585 vector2D vb(PointList[2*i] - PointList[2*fp],
586 PointList[2*i + 1] - PointList[2*fp+1]);
587
588 vector2D vn;
589 double l = vGetLengthOfNormal( &vb, &va, &vn );
590 if(l > lmax){
591 index = i;
592 lmax = l;
593 }
594 }
595 // If max distance is greater than epsilon, recursively simplify
596 if(lmax > epsilon){
597 keep->push_back(index);
598
599 // Recursive call
600 DouglasPeuckerM(PointList, fp, index, epsilon, keep);
601 DouglasPeuckerM(PointList, index, lp, epsilon, keep);
602
603 }
604 }
605
606
607 // CRC calculation for a byte buffer
608
609 static unsigned int crc_32_tab[] = { /* CRC polynomial 0xedb88320 */
610 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
611 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
612 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
613 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
614 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
615 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
616 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
617 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
618 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
619 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
620 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
621 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
622 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
623 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
624 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
625 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
626 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
627 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
628 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
629 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
630 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
631 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
632 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
633 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
634 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
635 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
636 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
637 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
638 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
639 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
640 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
641 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
642 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
643 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
644 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
645 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
646 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
647 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
648 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
649 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
650 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
651 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
652 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
653 };
654
655 #define UPDC32(octet,crc) (crc_32_tab[((crc)\
656 ^ ((unsigned char)octet)) & 0xff] ^ ((crc) >> 8))
657
658
crc32buf(unsigned char * buf,size_t len)659 unsigned int crc32buf(unsigned char *buf, size_t len)
660 {
661 unsigned int oldcrc32;
662
663 oldcrc32 = 0xFFFFFFFF;
664
665 for ( ; len; --len, ++buf)
666 {
667 oldcrc32 = UPDC32(*buf, oldcrc32);
668 }
669
670 return ~oldcrc32;
671
672 }
673