1. Jens Alfke
  2. MYUtilities

Source

MYUtilities / mnemonicode-0.73 / mnemonic.c

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
/* mnemonic.c

 Copyright (c) 2000  Oren Tirosh <oren@hishome.net>

 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:

 The above copyright notice and this permission notice shall be included in
 all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 THE SOFTWARE.

*/

#include "mnemonic.h"
#include <string.h>


/*
 * mn_words_required
 * 
 * Description:
 *  Calculate the number of words required to encode data using mnemonic
 *  encoding.
 *
 * Parameters:
 *  size - Size in bytes of data to be encoded
 * 
 * Return value:
 *  number of words required for the encoding
 */

int
mn_words_required (int size)
{
  return ((size + 1) * 3) / 4;
}


/*
 * mn_encode_word_index
 *
 * Description:
 *  Perform one step of encoding binary data into words. Returns word index.
 *
 * Parameters:
 *   src - Pointer to data buffer to encode
 *   srcsize - Size in bytes of data to encode 
 *   n - Sequence number of word to encode
 *       0 <= n < mn_words_required(srcsize)
 *
 * Return value:
 *   0 - no more words to encode / n is out of range
 *   1..MN_WORDS - word index. May be used as index to the mn_words[] array
 */

mn_index mn_encode_word_index (void *src, int srcsize, int n)
{
  mn_word32 x = 0;		/* Temporary for MN_BASE arithmetic */
  int offset;			/* Offset into src */
  int remaining;		/* Octets remaining to end of src */
  int extra = 0;		/* Index 7 extra words for 24 bit data */
  int i;

  if (n < 0 || n >= mn_words_required (srcsize))
    return 0;			/* word out of range */
  offset = (n / 3) * 4;		/* byte offset into src */
  remaining = srcsize - offset;
  if (remaining <= 0)
    return 0;
  if (remaining >= 4)
    remaining = 4;
  for (i = 0; i < remaining; i++)
    x |= ((mn_byte *) src)[offset + i] << (i * 8);	/* endianness-agnostic */

  switch (n % 3)
    {
    case 2:			/* Third word of group */
      if (remaining == 3)	/*  special case for 24 bits */
	extra = MN_BASE;	/*  use one of the 7 3-letter words */
      x /= (MN_BASE * MN_BASE);
      break;
    case 1:			/* Second word of group */
      x /= MN_BASE;
    }
  return x % MN_BASE + extra + 1;
}


/*
 * mn_encode_word
 *
 * Description:
 *  Perform one step of encoding binary data into words. Returns pointer 
 *  to word.
 *
 * Parameters:
 *   src - Pointer to data buffer to encode
 *   srcsize - Size of data to encode in bytes
 *   n - Sequence number of word to encode. 
 *       0 <= n < mn_words_required(srcsize)
 *
 * Return value:
 *   NULL - no more words to encode / n is out of range
 *   valid pointer - pointer to null-terminated lowercase word. length<=7
 */

const char *
mn_encode_word (void *src, int srcsize, int n)
{
  return mn_words[mn_encode_word_index (src, srcsize, n)];
}


/*
 * isletter
 * Utility function - returns nonzero if character c is an ASCII letter.
 */

static int
isletter (char c)
{
  return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}

/*
 * mn_next_word_index
 *
 * Description:
 *  Perform one step of decoding a null-terminated buffer into word indices.
 *  A word is defined as a sequence of letter character separated by one
 *  or more non-letter separator characters.
 *
 * Parameters:
 *  ptr - Pointer to a pointer to the next character in the buffer.
 *  *ptr is modified by the function; see Return Value below.
 *
 * Return value:
 *  0  - If *ptr==0 (points to the null at the end of the buffer) no more 
 *       words were found in the buffer. Otherwise *ptr points to beginning 
 *       of an unrecognized word.
 *  >0 - index of word found, suitable for decoding with mn_decode_word_index
 *       or comparison to values returned from mn_encode_index. *ptr points 
 *       to first character of next word or to terminating null.
 */

mn_index
mn_next_word_index (char **ptr)
{
  char *wordstart;
  char wordbuf[MN_WORD_BUFLEN];
  int i = 0;
  char c;
  mn_index idx;

  while (**ptr && !isletter (**ptr))	/* skip separator chars */
    (*ptr)++;
  wordstart = *ptr;		/* save for error reporting */
  while (**ptr && isletter (**ptr) && i < MN_WORD_BUFLEN - 1)
    {
      c = *(*ptr)++;
      if (c >= 'A' && c <= 'Z')
	c += 'a' - 'A';		/* convert to lowercase */
      wordbuf[i++] = c;
    }
  wordbuf[i] = '\0';
  while (**ptr && isletter (**ptr))	/* skip tail of long words */
    (*ptr)++;
  while (**ptr && !isletter (**ptr))	/* skip separators */
    (*ptr)++;

  if (wordbuf[0] == '\0')
    return 0;			/* EOF, no word found */

  for (idx = 1; idx <= MN_WORDS; idx++)
    {
      if (!strcmp (wordbuf, mn_words[idx]))
	return idx;
      /* FIXME: some fancy code should go here
         to accept misspellings and soundalikes.
         (replacing the linear search would also be nice) */
    }
  *ptr = wordstart;
  return 0;			/* not found */
}


/*
 * mn_decode_word_index
 *
 * Description:
 *  Perform one step of decoding a sequence of words into binary data.
 *
 * Parameters:
 *  index    - Index of word, e.g. return value of mn_next_word_index. Use
 *             the value MN_EOF(=0) to signal the end of input.
 *  dest     - Points to buffer to receive decoded binary result.
 *  destsize - Size of buffer 
 *  offset   - Pointer to an integer offset into the destination buffer for 
 *             next data byte. Initialize *offset to 0 before first call to 
 *             function. Modified by function and may be used as an 
 * 	       indication for the amount of data actually decoded.
 *
 * Return value:
 *  The return value indicates the status of the decoding function. It is
 *  ok to ignore this value on all calls to the function except the last
 *  one (with index=MN_EOF). Any errors encountered will be reported on. 
 *  the last call. The error code is also returned in *offset (negative 
 *  values indicate error).
 *
 * MN_OK (==0)	
 *	for index!=MN_EOF a return value of MN_OK means that 
 *	decoding has been successful so far.
 *	for index==MN_EOF a return value of MN_OK means that decoding
 *	of the entire buffer has been successful and the decoder is in
 *	a valid state for the end of the message. A total of *offset
 *	valid decoded bytes is in the buffer.
 *  MN_EREM      
 *	returned on MN_EOF when an unaccounted arithmetic remainder is
 *	in the decoder. Most likely indicates a truncated word sequence.
 *  MN_EOVERRUN	
 *	Not enough room in buffer for decoded data.
 *  MN_EOVERRUN24 
 *	Returned when decoding of data is attempted after decoding one
 *	of the 7 words reserved for 24 bit remainders at the end of the
 *	message. Probably indicates a garbled messages.
 *  MN_EINDEX	
 *	Bad input index. Naturally this should not happen when using 
 *	the result of mn_next_word_index.
 *  MN_EINDEX24
 *	Returned when one of the 7 words reserved for 24 bit remainders
 *	is received at an offset inappropriate for a 24 bit remainder.
 *  MN_EENCODING
 *	Indicates an overflow in MN_BASE arithmetic. Approximately 0.09%
 *	of the 3 word combinations are unused and will generate this error.
 */

int
mn_decode_word_index (mn_index index, void *dest, int destsize, int *offset)
{
  mn_word32 x;			/* Temporary for MN_BASE arithmetic */
  int groupofs;
  int i;

  if (*offset < 0)		/* Error from previous call? report it */
    return *offset;

  if (/*index < 0 ||*/ index > MN_WORDS)	/* Word index out of range */
    {
      *offset = MN_EINDEX;
      return *offset;
    }

  if (*offset > destsize)	/* out of range? */
    {
      *offset = MN_EOVERRUN;
      return *offset;
    }

  if (index > MN_BASE && *offset % 4 != 2)
    {				/* Unexpected 24 bit remainder word */
      *offset = MN_EINDEX24;
      return *offset;
    }

  groupofs = *offset & ~3;	/* Offset of 4 byte group containing offet */
  x = 0;
  for (i = 0; i < 4; i++)
    if (groupofs + i < destsize)	/* Ignore any bytes outside buffer */
      x |= ((mn_byte *) dest)[groupofs + i] << (i * 8);	/* assemble number */

  if (index == MN_EOF)		/* Got EOF signal */
    {
      switch (*offset % 4)
	{
	case 3:		/* group was three words and the last */
	  return MN_OK;		/*  word was a 24 bit remainder */
	case 2:		/* last group has two words */
	  if (x <= 0xFFFF)	/*  should encode 16 bit data */
	    return MN_OK;
	  else
	    {
	      *offset = MN_EREM;
	      return *offset;
	    }
	case 1:		/* last group has just one word */
	  if (x <= 0xFF)	/*  should encode 8 bits */
	    return MN_OK;
	  else
	    {
	      *offset = MN_EREM;
	      return *offset;
	    }

	case 0:		/* last group was full 3 words */
	  return MN_OK;
	}
    }
  if (*offset == destsize)	/* At EOF but didn't get MN_EOF */
    {
      *offset = MN_EOVERRUN;
      return *offset;
    }

  index--;			/* 1 based to 0 based index */

  switch (*offset % 4)
    {
    case 3:			/* Got data past 24 bit remainder */
      *offset = MN_EOVERRUN24;
      return *offset;
    case 2:
      if (index >= MN_BASE)
	{			/* 24 bit remainder */
	  x += (index - MN_BASE) * MN_BASE * MN_BASE;
	  (*offset)++;		/* *offset%4 == 3 for next time */
	}
      else
	{			/* catch invalid encodings */
	  if (index >= 1625 || (index == 1624 && x > 1312671))
	    {
	      *offset = MN_EENCODING;
	      return *offset;
	    }
	  x += index * MN_BASE * MN_BASE;
	  (*offset) += 2;	/* *offset%4 == 0 for next time */
	}
      break;
    case 1:
      x += index * MN_BASE;
      (*offset)++;
      break;
    case 0:
      x = index;
      (*offset)++;
      break;
    }

  for (i = 0; i < 4; i++)
    if (groupofs + i < destsize)	/* Don't step outside the buffer */
      {
	((mn_byte *) dest)[groupofs + i] = (mn_byte) x % 256;
	x /= 256;
      }
  return MN_OK;
}

/*
 * mn_encode
 *
 * Description:
 *  Encode a binary data buffer into a null-terminated sequence of words.
 *  The word separators are taken from the format string. 
 *
 * Parameters:
 *  src      - Pointer to the beginning of the binary data buffer.
 *  srcsize  - Size in bytes of binary data buffer
 *  dest     - Pointer to the beginning of a character buffer 
 *  destsize - Size in characters of character buffer
 *  format   - Null-terminated string describing the output format.
 *             In the format string any letter or sequence of letters
 *             acts as a placeholder for the encoded words. The word 
 *             placeholders are separated by one or more non-letter
 *             characters. When the encoder reaches the end of the 
 *             format string it starts reading it again.
 *             For sample formats see MN_F* constants in mnemonic.h
 *	       If format is empty or NULL the format MN_FDEFAULT
 *	       is used.
 *
 * Return value:
 *  MN_OK(=0)
 *	Encoding was successful.
 *  MN_EOVERRUN
 *	Output size exceeds size of destination buffer
 *  MN_EFORMAT
 *	Invalid format string. This function enforces formats which
 *	will result in a string which can be successfully decoded by
 *	the mn_decode function.
 */

int
mn_encode (void *src, int srcsize, char *dest, int destsize, char *format)
{
  int n;
  char *fmt;
  char *destend = dest + destsize;
  const char *word;

  if (format == 0 || format[0] == '\0')
    format = MN_FDEFAULT;
  fmt = format;
  for (n = 0; n < mn_words_required (srcsize); n++)
    {
      while (dest < destend && *fmt != '\0' && !isletter (*fmt))
	*dest++ = *fmt++;
      if (dest >= destend)
	return MN_EOVERRUN;
      if (*fmt == '\0')
	{
	  if (isletter (fmt[-1]) && isletter (format[0]))
	    return MN_EFORMAT;
	  fmt = format;
	  while (dest < destend && *fmt != '\0' && !isletter (*fmt))
	    *dest++ = *fmt++;
	  if (!isletter (*fmt))
	    return MN_EFORMAT;
	}
      word = mn_encode_word (src, srcsize, n);
      if (word == 0)
	return MN_EOVERRUN;	/* shouldn't happen, actually */

      while (isletter (*fmt))
	fmt++;
      while (dest < destend && *word != '\0')
	*dest++ = *word++;
    }
  if (dest < destend)
    *dest++ = '\0';
  else
    return MN_EOVERRUN;
  return MN_OK;
}

/*
 * mn_decode
 *
 * Description:
 *  Decode a text representation in null-terminated character buffer src to 
 *  binary buffer dest.
 *
 * Parameters:
 *  src      - Pointer to null-terminated character buffer 
 *  dest     - Pointer to beginning of destination buffer
 *  destsize - Size in bytes of destination buffer
 *
 * Return value:
 *  This function may return all the value returned by mn_decode_word_index
 *  plus the following result code:
 *
 * MN_EWORD  - Unrecognized word.
 */

int
mn_decode (char *src, void *dest, int destsize)
{
  mn_index index;
  int offset = 0;

  while ((index = mn_next_word_index (&src)) != 0)
    {
      if (index == 0 && *src != 0)
	return MN_EWORD;
      (void) mn_decode_word_index (index, dest, destsize, &offset);
    }
  (void) mn_decode_word_index (MN_EOF, dest, destsize, &offset);
  return offset;
}