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