1/* 2 * rs_ecc.c -- 3 * 4 * Implements and registers error correction with Reed-Solomon (255,249,7) block code. 5 * 6 * 7 * Copyright (c) 1996 Andreas Kupries (a.kupries@westend.com) 8 * All rights reserved. 9 * 10 * Permission is hereby granted, without written agreement and without 11 * license or royalty fees, to use, copy, modify, and distribute this 12 * software and its documentation for any purpose, provided that the 13 * above copyright notice and the following two paragraphs appear in 14 * all copies of this software. 15 * 16 * IN NO EVENT SHALL I LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, 17 * INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS 18 * SOFTWARE AND ITS DOCUMENTATION, EVEN IF I HAVE BEEN ADVISED OF THE 19 * POSSIBILITY OF SUCH DAMAGE. 20 * 21 * I SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 22 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND 24 * I HAVE NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, 25 * ENHANCEMENTS, OR MODIFICATIONS. 26 * 27 * CVS: $Id: rs_ecc.c,v 1.10 2009/05/07 04:57:27 andreas_kupries Exp $ 28 */ 29 30#include "transformInt.h" 31 32/* 33 * Forward declaractions of internally used procedures. 34 */ 35 36#define MSG_LEN (249) /* 248 bytes usable, 1 byte length information 37 * (always at end of block) */ 38#define CODE_LEN (255) 39 40void rsencode _ANSI_ARGS_ ((unsigned char m [MSG_LEN], 41 unsigned char c [CODE_LEN])); 42void rsdecode _ANSI_ARGS_ ((unsigned char c [CODE_LEN], 43 unsigned char m [MSG_LEN], int* errcode)); 44 45/* 46 * Declarations of internal procedures. 47 */ 48 49static Trf_ControlBlock CreateEncoder _ANSI_ARGS_ ((ClientData writeClientData, 50 Trf_WriteProc *fun, 51 Trf_Options optInfo, 52 Tcl_Interp* interp, 53 ClientData clientData)); 54static void DeleteEncoder _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 55 ClientData clientData)); 56static int Encode _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 57 unsigned int character, 58 Tcl_Interp* interp, 59 ClientData clientData)); 60static int EncodeBuffer _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 61 unsigned char* buffer, int bufLen, 62 Tcl_Interp* interp, 63 ClientData clientData)); 64static int FlushEncoder _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 65 Tcl_Interp* interp, 66 ClientData clientData)); 67static void ClearEncoder _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 68 ClientData clientData)); 69 70static Trf_ControlBlock CreateDecoder _ANSI_ARGS_ ((ClientData writeClientData, 71 Trf_WriteProc *fun, 72 Trf_Options optInfo, 73 Tcl_Interp* interp, 74 ClientData clientData)); 75static void DeleteDecoder _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 76 ClientData clientData)); 77static int Decode _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 78 unsigned int character, 79 Tcl_Interp* interp, 80 ClientData clientData)); 81static int DecodeBuffer _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 82 unsigned char* buffer, int bufLen, 83 Tcl_Interp* interp, 84 ClientData clientData)); 85static int FlushDecoder _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 86 Tcl_Interp* interp, 87 ClientData clientData)); 88static void ClearDecoder _ANSI_ARGS_ ((Trf_ControlBlock ctrlBlock, 89 ClientData clientData)); 90 91 92/* 93 * Converter definition. 94 */ 95 96static Trf_TypeDefinition convDefinition = 97{ 98 "rs_ecc", 99 NULL, /* filled by TrfInit_RS_ECC, THREADING: serialize initialization */ 100 NULL, /* not used */ 101 { 102 CreateEncoder, 103 DeleteEncoder, 104 Encode, 105 EncodeBuffer, 106 FlushEncoder, 107 ClearEncoder, 108 NULL /* no MaxRead */ 109 }, { 110 CreateDecoder, 111 DeleteDecoder, 112 Decode, 113 DecodeBuffer, 114 FlushDecoder, 115 ClearDecoder, 116 NULL /* no MaxRead */ 117 }, 118 TRF_RATIO (248, 255) 119}; 120 121/* 122 * Definition of the control blocks for en- and decoder. 123 */ 124 125typedef struct _EncoderControl_ { 126 Trf_WriteProc* write; 127 ClientData writeClientData; 128 129 /* add conversion specific items here (RS_ECC) */ 130 131 unsigned char block [MSG_LEN]; 132 unsigned char charCount; 133 134} EncoderControl; 135 136 137typedef struct _DecoderControl_ { 138 Trf_WriteProc* write; 139 ClientData writeClientData; 140 141 /* add conversion specific items here (RS_ECC) */ 142 143 unsigned char block [CODE_LEN]; 144 unsigned char charCount; 145 146} DecoderControl; 147 148 149 150 151/* 152 *------------------------------------------------------* 153 * 154 * TrfInit_RS_ECC -- 155 * 156 * ------------------------------------------------* 157 * Register the ECC algorithm implemented in this file. 158 * ------------------------------------------------* 159 * 160 * Sideeffects: 161 * As of 'Trf_Register'. 162 * 163 * Result: 164 * A standard Tcl error code. 165 * 166 *------------------------------------------------------* 167 */ 168 169int 170TrfInit_RS_ECC (interp) 171Tcl_Interp* interp; 172{ 173 TrfLock; /* THREADING: serialize initialization */ 174 convDefinition.options = Trf_ConverterOptions (); 175 TrfUnlock; 176 177 return Trf_Register (interp, &convDefinition); 178} 179 180/* 181 *------------------------------------------------------* 182 * 183 * CreateEncoder -- 184 * 185 * ------------------------------------------------* 186 * Allocate and initialize the control block of a 187 * data encoder. 188 * ------------------------------------------------* 189 * 190 * Sideeffects: 191 * Allocates memory. 192 * 193 * Result: 194 * An opaque reference to the control block. 195 * 196 *------------------------------------------------------* 197 */ 198 199static Trf_ControlBlock 200CreateEncoder (writeClientData, fun, optInfo, interp, clientData) 201ClientData writeClientData; 202Trf_WriteProc *fun; 203Trf_Options optInfo; 204Tcl_Interp* interp; 205ClientData clientData; 206{ 207 EncoderControl* c; 208 209 c = (EncoderControl*) ckalloc (sizeof (EncoderControl)); 210 c->write = fun; 211 c->writeClientData = writeClientData; 212 213 /* initialize conversion specific items here (RS_ECC) */ 214 215 memset (c->block, '\0', MSG_LEN); 216 c->charCount = 0; 217 218 return (ClientData) c; 219} 220 221/* 222 *------------------------------------------------------* 223 * 224 * DeleteEncoder -- 225 * 226 * ------------------------------------------------* 227 * Destroy the control block of an encoder. 228 * ------------------------------------------------* 229 * 230 * Sideeffects: 231 * Releases the memory allocated by 'CreateEncoder' 232 * 233 * Result: 234 * None. 235 * 236 *------------------------------------------------------* 237 */ 238 239static void 240DeleteEncoder (ctrlBlock, clientData) 241Trf_ControlBlock ctrlBlock; 242ClientData clientData; 243{ 244 EncoderControl* c = (EncoderControl*) ctrlBlock; 245 246 /* release conversion specific items here (RS_ECC) */ 247 248 ckfree ((char*) c); 249} 250 251/* 252 *------------------------------------------------------* 253 * 254 * Encode -- 255 * 256 * ------------------------------------------------* 257 * Encode the given character and write the result. 258 * ------------------------------------------------* 259 * 260 * Sideeffects: 261 * As of the called WriteFun. 262 * 263 * Result: 264 * Generated bytes implicitly via WriteFun. 265 * A standard Tcl error code. 266 * 267 *------------------------------------------------------* 268 */ 269 270static int 271Encode (ctrlBlock, character, interp, clientData) 272Trf_ControlBlock ctrlBlock; 273unsigned int character; 274Tcl_Interp* interp; 275ClientData clientData; 276{ 277 EncoderControl* c = (EncoderControl*) ctrlBlock; 278 279 /* execute conversion specific code here (RS_ECC) */ 280 281 c->block [c->charCount] = character; 282 c->charCount ++; 283 284 if (c->charCount == (MSG_LEN-1)) { 285 char out [CODE_LEN]; 286 287 c->block [MSG_LEN-1] = c->charCount; /* == MSG_LEN-1 */ 288 289 rsencode (c->block, (unsigned char*) out); 290 291 /* not really required: memset (c->block, '\0', MSG_LEN); */ 292 c->charCount = 0; 293 294 return c->write (c->writeClientData, (unsigned char*) out, CODE_LEN, interp); 295 } 296 297 return TCL_OK; 298} 299 300/* 301 *------------------------------------------------------* 302 * 303 * EncodeBuffer -- 304 * 305 * ------------------------------------------------* 306 * Encode the given buffer and write the result. 307 * ------------------------------------------------* 308 * 309 * Sideeffects: 310 * As of the called WriteFun. 311 * 312 * Result: 313 * Generated bytes implicitly via WriteFun. 314 * A standard Tcl error code. 315 * 316 *------------------------------------------------------* 317 */ 318 319static int 320EncodeBuffer (ctrlBlock, buffer, bufLen, interp, clientData) 321Trf_ControlBlock ctrlBlock; 322unsigned char* buffer; 323int bufLen; 324Tcl_Interp* interp; 325ClientData clientData; 326{ 327 EncoderControl* c = (EncoderControl*) ctrlBlock; 328 329 /* execute conversion specific code here (RS_ECC) */ 330 331 char out [CODE_LEN], oldchar; 332 int res; 333 334 /* 335 * Complete chunk with incoming data, generate EC-information, 336 * then use all chunks contained in the buffer. Remember 337 * an incomplete chunk and wait for further calls. 338 */ 339 340 int k = (MSG_LEN-1) - c->charCount; 341 342 if (k > bufLen) { 343 /* 344 * We got less information than required to form a full block. 345 * Extend the internal buffer and wait for more. 346 */ 347 memcpy ((VOID*) (c->block + c->charCount), (VOID*) buffer, bufLen); 348 c->charCount += bufLen; 349 return TCL_OK; 350 } 351 352 if (k < (MSG_LEN-1)) { 353 memcpy ((VOID*) (c->block + c->charCount), (VOID*) buffer, k); 354 355 c->block [MSG_LEN-1] = c->charCount; /* == MSG_LEN-1 */ 356 357 rsencode (c->block, (unsigned char*) out); 358 359 c->charCount = 0; 360 361 res = c->write (c->writeClientData, (unsigned char*) out, CODE_LEN, interp); 362 363 buffer += k; 364 bufLen -= k; 365 366 if (res != TCL_OK) 367 return res; 368 } /* k == (MSG_LEN-1) => internal buffer was empty, so skip it entirely */ 369 370 371 372 while (bufLen > (MSG_LEN-1)) { 373 /* 374 * We are directly manipulating the buffer to get the charCount 375 * of the individual chunks into it. To avoid memory overuns we 376 * query for '>' at the begin of the loop and handle the special 377 * case of 'bufLen == MSG_LEN-1' afterward. 378 */ 379 380 oldchar = buffer [MSG_LEN-1]; 381 buffer [MSG_LEN-1] = (unsigned char) (MSG_LEN-1); 382 383 rsencode (buffer, (unsigned char*) out); 384 385 buffer [MSG_LEN-1] = oldchar; 386 387 res = c->write (c->writeClientData, (unsigned char*) out, CODE_LEN, interp); 388 389 buffer += MSG_LEN-1; 390 bufLen -= MSG_LEN-1; 391 392 if (res != TCL_OK) 393 return res; 394 } 395 396 memcpy ((VOID*) c->block, (VOID*) buffer, bufLen); 397 c->charCount = bufLen; 398 399 if (bufLen == (MSG_LEN-1)) { 400 c->block [MSG_LEN-1] = c->charCount; /* == MSG_LEN-1 */ 401 402 rsencode (c->block, (unsigned char*) out); 403 404 c->charCount = 0; 405 406 return c->write (c->writeClientData, (unsigned char*) out, CODE_LEN, interp); 407 } /* else: nothing more to do to remember incomplete data */ 408 409 return TCL_OK; 410} 411 412/* 413 *------------------------------------------------------* 414 * 415 * FlushEncoder -- 416 * 417 * ------------------------------------------------* 418 * Encode an incomplete character sequence (if possible). 419 * ------------------------------------------------* 420 * 421 * Sideeffects: 422 * As of the called WriteFun. 423 * 424 * Result: 425 * Generated bytes implicitly via WriteFun. 426 * A standard Tcl error code. 427 * 428 *------------------------------------------------------* 429 */ 430 431static int 432FlushEncoder (ctrlBlock, interp, clientData) 433Trf_ControlBlock ctrlBlock; 434Tcl_Interp* interp; 435ClientData clientData; 436{ 437 EncoderControl* c = (EncoderControl*) ctrlBlock; 438 439 /* execute conversion specific code here (RS_ECC) */ 440 441 if (c->charCount > 0) { 442 char out [CODE_LEN]; 443 444 c->block [MSG_LEN-1] = c->charCount; /* < (MSG_LEN-1) */ 445 446 rsencode (c->block, (unsigned char*) out); 447 448 return c->write (c->writeClientData, (unsigned char*) out, CODE_LEN, interp); 449 } 450 451 return TCL_OK; 452} 453 454/* 455 *------------------------------------------------------* 456 * 457 * ClearEncoder -- 458 * 459 * ------------------------------------------------* 460 * Discard an incomplete character sequence. 461 * ------------------------------------------------* 462 * 463 * Sideeffects: 464 * See above. 465 * 466 * Result: 467 * None. 468 * 469 *------------------------------------------------------* 470 */ 471 472static void 473ClearEncoder (ctrlBlock, clientData) 474Trf_ControlBlock ctrlBlock; 475ClientData clientData; 476{ 477 EncoderControl* c = (EncoderControl*) ctrlBlock; 478 479 /* execute conversion specific code here (RS_ECC) */ 480 481 memset (c->block, '\0', MSG_LEN); 482 c->charCount = 0; 483} 484 485/* 486 *------------------------------------------------------* 487 * 488 * CreateDecoder -- 489 * 490 * ------------------------------------------------* 491 * Allocate and initialize the control block of a 492 * data decoder. 493 * ------------------------------------------------* 494 * 495 * Sideeffects: 496 * Allocates memory. 497 * 498 * Result: 499 * An opaque reference to the control block. 500 * 501 *------------------------------------------------------* 502 */ 503 504static Trf_ControlBlock 505CreateDecoder (writeClientData, fun, optInfo, interp, clientData) 506ClientData writeClientData; 507Trf_WriteProc *fun; 508Trf_Options optInfo; 509Tcl_Interp* interp; 510ClientData clientData; 511{ 512 DecoderControl* c; 513 514 c = (DecoderControl*) ckalloc (sizeof (DecoderControl)); 515 c->write = fun; 516 c->writeClientData = writeClientData; 517 518 /* initialize conversion specific items here (RS_ECC) */ 519 520 memset (c->block, '\0', CODE_LEN); 521 c->charCount = 0; 522 523 return (ClientData) c; 524} 525 526/* 527 *------------------------------------------------------* 528 * 529 * DeleteDecoder -- 530 * 531 * ------------------------------------------------* 532 * Destroy the control block of an decoder. 533 * ------------------------------------------------* 534 * 535 * Sideeffects: 536 * Releases the memory allocated by 'CreateDecoder' 537 * 538 * Result: 539 * None. 540 * 541 *------------------------------------------------------* 542 */ 543 544static void 545DeleteDecoder (ctrlBlock, clientData) 546Trf_ControlBlock ctrlBlock; 547ClientData clientData; 548{ 549 DecoderControl* c = (DecoderControl*) ctrlBlock; 550 551 /* release conversion specific items here (RS_ECC) */ 552 553 ckfree ((char*) c); 554} 555 556/* 557 *------------------------------------------------------* 558 * 559 * Decode -- 560 * 561 * ------------------------------------------------* 562 * Decode the given character and write the result. 563 * ------------------------------------------------* 564 * 565 * Sideeffects: 566 * As of the called WriteFun. 567 * 568 * Result: 569 * Generated bytes implicitly via WriteFun. 570 * A standard Tcl error code. 571 * 572 *------------------------------------------------------* 573 */ 574 575static int 576Decode (ctrlBlock, character, interp, clientData) 577Trf_ControlBlock ctrlBlock; 578unsigned int character; 579Tcl_Interp* interp; 580ClientData clientData; 581{ 582 DecoderControl* c = (DecoderControl*) ctrlBlock; 583 584 /* execute conversion specific code here (RS_ECC) */ 585 586 c->block [c->charCount] = character; 587 c->charCount ++; 588 589 if (c->charCount == CODE_LEN) { 590 unsigned char msg [MSG_LEN]; 591 int err; 592 int length; 593 594 rsdecode (c->block, msg, &err); 595 /* should check decoder result */ 596 597 /* not really required: memset (c->block, '\0', CODE_LEN); */ 598 c->charCount = 0; 599 600 length = msg [MSG_LEN-1]; /* <= (MSG_LEN-1) */ 601 602 /* restrict length to legal range. 603 * unrecoverable errors could have destroyed this information too! 604 */ 605 606 if (length > (MSG_LEN-1)) 607 length = MSG_LEN-1; 608 609 return c->write (c->writeClientData, msg, length, interp); 610 } 611 612 return TCL_OK; 613} 614 615/* 616 *------------------------------------------------------* 617 * 618 * DecodeBuffer -- 619 * 620 * ------------------------------------------------* 621 * Decode the given buffer and write the result. 622 * ------------------------------------------------* 623 * 624 * Sideeffects: 625 * As of the called WriteFun. 626 * 627 * Result: 628 * Generated bytes implicitly via WriteFun. 629 * A standard Tcl error code. 630 * 631 *------------------------------------------------------* 632 */ 633 634static int 635DecodeBuffer (ctrlBlock, buffer, bufLen, interp, clientData) 636Trf_ControlBlock ctrlBlock; 637unsigned char* buffer; 638int bufLen; 639Tcl_Interp* interp; 640ClientData clientData; 641{ 642 DecoderControl* c = (DecoderControl*) ctrlBlock; 643 644 /* execute conversion specific code here (RS_ECC) */ 645 646 unsigned char msg [MSG_LEN]; 647 int err, length, res; 648 649 /* 650 * Complete chunk with incoming data, generate EC-information, 651 * then use all chunks contained in the buffer. Remember 652 * an incomplete chunk and wait for further calls. 653 */ 654 655 int k = (CODE_LEN-1) - c->charCount; 656 657 if (k > bufLen) { 658 /* 659 * We got less information than required to form a full block. 660 * Extend the internal buffer and wait for more. 661 */ 662 memcpy ((VOID*) (c->block + c->charCount), (VOID*) buffer, bufLen); 663 c->charCount += bufLen; 664 return TCL_OK; 665 } 666 667 if (k < (CODE_LEN-1)) { 668 memcpy ((VOID*) (c->block + c->charCount), (VOID*) buffer, k); 669 670 rsdecode (c->block, msg, &err); 671 672 length = msg [MSG_LEN-1]; /* <= (MSG_LEN-1) */ 673 674 /* restrict length to legal range. 675 * unrecoverable errors could have destroyed this information too! 676 */ 677 678 if (length > (MSG_LEN-1)) 679 length = MSG_LEN-1; 680 681 res = c->write (c->writeClientData, msg, length, interp); 682 683 c->charCount = 0; 684 685 buffer += k; 686 bufLen -= k; 687 688 if (res != TCL_OK) 689 return res; 690 } /* k == (MSG_LEN-1) => internal buffer was empty, so skip it entirely */ 691 692 693 694 while (bufLen >= CODE_LEN) { 695 696 rsdecode (buffer, msg, &err); 697 /* should check decoder result */ 698 699 length = msg [MSG_LEN-1]; /* <= (MSG_LEN-1) */ 700 701 /* restrict length to legal range. 702 * unrecoverable errors could have destroyed this information too! 703 */ 704 705 if (length > (MSG_LEN-1)) 706 length = MSG_LEN-1; 707 708 res = c->write (c->writeClientData, msg, length, interp); 709 710 buffer += CODE_LEN; 711 bufLen -= CODE_LEN; 712 713 if (res != TCL_OK) 714 return res; 715 } 716 717 718 if (bufLen > 0) { 719 memcpy ((VOID*) c->block, (VOID*) buffer, bufLen); 720 c->charCount = bufLen; 721 } 722 723 return TCL_OK; 724} 725 726/* 727 *------------------------------------------------------* 728 * 729 * FlushDecoder -- 730 * 731 * ------------------------------------------------* 732 * Decode an incomplete character sequence (if possible). 733 * ------------------------------------------------* 734 * 735 * Sideeffects: 736 * As of the called WriteFun. 737 * 738 * Result: 739 * Generated bytes implicitly via WriteFun. 740 * A standard Tcl error code. 741 * 742 *------------------------------------------------------* 743 */ 744 745static int 746FlushDecoder (ctrlBlock, interp, clientData) 747Trf_ControlBlock ctrlBlock; 748Tcl_Interp* interp; 749ClientData clientData; 750{ 751 DecoderControl* c = (DecoderControl*) ctrlBlock; 752 753 /* execute conversion specific code here (RS_ECC) */ 754 755 if (c->charCount > 0) { 756 if (interp != NULL) { 757 Tcl_AppendResult (interp, "can not decode incomplete block at end of input", (char*) NULL); 758 } 759 760 return TCL_ERROR; 761 } 762 763 return TCL_OK; 764} 765 766/* 767 *------------------------------------------------------* 768 * 769 * ClearDecoder -- 770 * 771 * ------------------------------------------------* 772 * Discard an incomplete character sequence. 773 * ------------------------------------------------* 774 * 775 * Sideeffects: 776 * See above. 777 * 778 * Result: 779 * None. 780 * 781 *------------------------------------------------------* 782 */ 783 784static void 785ClearDecoder (ctrlBlock, clientData) 786Trf_ControlBlock ctrlBlock; 787ClientData clientData; 788{ 789 DecoderControl* c = (DecoderControl*) ctrlBlock; 790 791 /* execute conversion specific code here (RS_ECC) */ 792 793 memset (c->block, '\0', CODE_LEN); 794 c->charCount = 0; 795} 796 797/* 798 * External code from here on. 799 */ 800 801/* #include rs-ecc / *.c: THREADING: import of three constant vars, read-only => safe */ 802#include "rs-ecc/gflib.c" 803#include "rs-ecc/rslib.c" 804