1 /* -*-c-*- ------------------ mix_types.c :
2 * Implementation file for mix_types.h declarations.
3 * ------------------------------------------------------------------
4 * Copyright (C) 2000, 2001, 2002, 2004, 2006, 2007, 2019 Free Software Foundation, Inc.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 *
20 */
21
22 #include "mix.h"
23 #include <limits.h>
24 #include <ctype.h>
25 #include "mix_types.h"
26
27
28 /*------------------------ initialisation stuff ------------------------*/
29 /* flag telling whether a field spec is valid */
30 static gboolean is_bad_field_[MIX_BYTE_MAX + 1];
31 /* shift associated with a fspec */
32 static guint shift_[MIX_BYTE_MAX + 1];
33 /* mask associated with a fspec */
34 static glong mask_[MIX_BYTE_MAX + 1];
35
36 /* maps from gchar's to mix_char_t */
37 #define NONP_ (guchar)('?')
38 static mix_char_t ascii_to_mix_char_[UCHAR_MAX + 1];
39 static guchar mix_char_to_ascii_[MIX_CHAR_MAX + 1] = {
40 ' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', '~', 'J',
41 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', '[', '#', 'S', 'T',
42 'U', 'V', 'W', 'X', 'Y', 'Z', '0', '1', '2', '3', '4', '5', '6',
43 '7', '8', '9', '.', ',', '(', ')', '+', '-', '*', '/', '=', '$',
44 '<', '>', '@', ';', ':', '\''
45 };
46
47
48 /* initialise the above arrays */
49 void
mix_init_types(void)50 mix_init_types (void)
51 {
52 guint lt, rt;
53 for (lt = 0; lt < 8; ++lt)
54 for (rt = 0; rt < 8; ++rt)
55 {
56 guint F = 8 * lt + rt;
57 is_bad_field_[F] = rt < lt || 5 < rt;
58 if ( is_bad_field_[F] )
59 shift_[F] = 0, mask_[F] = 0;
60 else
61 {
62 guint width = rt - (lt == 0 ? 1 : lt) + 1;
63 shift_[F] = 6 * (5 - rt);
64 mask_[F] = ((1L << (6 * width)) - 1) << shift_[F];
65 }
66 }
67
68 for ( lt = 0; lt < UCHAR_MAX + 1; ++lt )
69 ascii_to_mix_char_[lt] = NONP_;
70 for ( lt = 0; lt < MIX_CHAR_MAX + 1; ++lt )
71 ascii_to_mix_char_[mix_char_to_ascii_[lt]] = (guchar)lt;
72 }
73
74 mix_char_t
mix_ascii_to_char(guchar c)75 mix_ascii_to_char (guchar c)
76 {
77 return ascii_to_mix_char_[toupper (c)];
78 }
79
80
81 guchar
mix_char_to_ascii(mix_char_t c)82 mix_char_to_ascii (mix_char_t c)
83 {
84 return c > MIX_CHAR_MAX ? NONP_ : mix_char_to_ascii_[c];
85 }
86
87
88 /*---------------------------- m_word_t --------------------------------- */
89
90 /* Create mix_word_t from an array of mix_byte_t */
91 mix_word_t
mix_bytes_to_word(mix_byte_t * bytes,guint byteno)92 mix_bytes_to_word (mix_byte_t *bytes, guint byteno)
93 {
94 mix_word_t result = 0;
95 guint k;
96
97 g_return_val_if_fail (bytes != NULL, MIX_WORD_ZERO);
98 g_return_val_if_fail (byteno != 0, MIX_WORD_ZERO);
99
100 if ( byteno > 5 ) byteno = 5;
101 for ( k = 0; k < byteno; k++ )
102 result |= ((gulong)bytes[k]) << (6*(byteno-k-1));
103
104 return result;
105 }
106
107
108 /* Field operations */
109 mix_word_t /* the specified field or 0 if f is not valid */
mix_word_get_field(mix_fspec_t f,mix_word_t word)110 mix_word_get_field (mix_fspec_t f, mix_word_t word)
111 {
112 mix_word_t result;
113
114 g_return_val_if_fail (!is_bad_field_[f],MIX_WORD_ZERO);
115
116 result = ( (word & mask_[f]) >> shift_[f] );
117 if (f < 8) /* if f is of the form (0:R), retain the sign of word */
118 result |= mix_word_sign (word);
119
120 return result;
121 }
122
123
124 mix_word_t
mix_word_set_field(mix_fspec_t f,mix_word_t from,mix_word_t to)125 mix_word_set_field (mix_fspec_t f, mix_word_t from, mix_word_t to)
126 {
127 mix_word_t result;
128 glong m = mask_[f];
129
130 g_return_val_if_fail (!is_bad_field_[f],to);
131
132 if (f < 8) /* if F is of the form (0:R), use the sign of -from- */
133 result = (to & ~m & ~MIX_WORD_SIGN_BIT)
134 | ((from /*<< shift_[f]*/) & m) | mix_word_sign (from);
135 else
136 result = (to & ~m) | ((from /*<< shift_[f]*/) & m);
137
138 return result;
139 }
140
141 mix_word_t
mix_word_store_field(mix_fspec_t f,mix_word_t from,mix_word_t to)142 mix_word_store_field (mix_fspec_t f, mix_word_t from, mix_word_t to)
143 {
144 mix_word_t result;
145 glong m = mask_[f];
146
147 g_return_val_if_fail (!is_bad_field_[f],to);
148
149 if (f < 8) /* if F is of the form (0:R), use the sign of -from- */
150 result = (to & ~m & ~MIX_WORD_SIGN_BIT)
151 | ((from << shift_[f]) & m) | mix_word_sign (from);
152 else
153 result = (to & ~m) | ((from << shift_[f]) & m);
154
155 return result;
156 }
157
158
159
160 gboolean
mix_fspec_is_valid(mix_fspec_t f)161 mix_fspec_is_valid (mix_fspec_t f)
162 {
163 return !(is_bad_field_[f]);
164 }
165
166 mix_byte_t
mix_word_get_byte(mix_word_t word,guint idx)167 mix_word_get_byte (mix_word_t word, /* word parsed */
168 guint idx /* byte: 1 to 5 */ )
169 {
170 mix_byte_t fspec = mix_fspec_new (idx,idx);
171
172 g_return_val_if_fail ((idx > 0 && idx < 6), MIX_BYTE_ZERO);
173
174 return mix_byte_new (mix_word_get_field (fspec,word));
175 }
176
177
178 extern void
mix_word_set_byte(mix_word_t * into,guint idx,mix_byte_t value)179 mix_word_set_byte (mix_word_t *into, guint idx, mix_byte_t value)
180 {
181 mix_word_t from = value;
182 mix_byte_t fspec = mix_fspec_new (idx,idx);
183
184 g_return_if_fail (into != NULL);
185 g_return_if_fail (idx > 0 && idx < 6);
186
187 from <<= shift_[fspec];
188 *into = mix_word_set_field (fspec,from,*into);
189 }
190
191 /* Arithmetic operations */
192 mix_word_t
mix_word_add(mix_word_t x,mix_word_t y)193 mix_word_add (mix_word_t x, mix_word_t y)
194 {
195 static const gulong MIX_WORD_MAX_SIM = 2*MIX_WORD_MAX + 1;
196
197 gint32 result;
198 if ( mix_word_sign (x) == mix_word_sign (y) )
199 {
200 result = (mix_word_magnitude (x) + mix_word_magnitude (y));
201 if ( result > MIX_WORD_MAX ) {
202 /* for instance MIX_WORD_MAX + 1 = - MIX_WORD_MAX */
203 result = MIX_WORD_MAX_SIM - result;
204 result |= mix_word_sign (mix_word_negative (x));
205 } else {
206 result |= mix_word_sign (x);
207 }
208 }
209 else
210 {
211 result = mix_word_magnitude (x) - mix_word_magnitude (y);
212 if (result < 0)
213 result = -result|mix_word_sign (y);
214 else
215 result = result|mix_word_sign (x);
216 }
217
218 g_assert ( result >= 0 );
219
220 return (mix_word_t)result;
221 }
222
223 gboolean /* TRUE if overflow */
mix_word_add_and_carry(mix_word_t x,mix_word_t y,mix_word_t * h,mix_word_t * l)224 mix_word_add_and_carry (mix_word_t x, mix_word_t y,
225 mix_word_t *h, mix_word_t *l)
226 {
227 gboolean result;
228
229 if ( mix_word_sign (x) == mix_word_sign (y) )
230 {
231 guint32 sum = (mix_word_magnitude (x) + mix_word_magnitude (y));
232 if ( sum > MIX_WORD_MAX )
233 {
234 result = TRUE;
235 if ( l != NULL )
236 {
237 *l = sum - MIX_WORD_MAX -1;
238 *l |= mix_word_sign (x);
239 }
240 if ( h != NULL )
241 {
242 *h = sum >> 30;
243 *h |= mix_word_sign (x);
244 }
245 }
246 else /* sum <= MIX_WORD_MAX */
247 {
248 result = FALSE;
249 if ( h != NULL ) *h = 0;
250 if ( l != NULL )
251 {
252 *l = sum;
253 if ( sum != 0 )
254 *l |= mix_word_sign (x);
255 /* keep positive sign for 0 so that w - w == -w + w */
256 }
257 }
258 }
259 else /* mix_word_sign (x) != mix_word_sign (y) */
260 {
261 result = FALSE;
262 if ( h != NULL ) *h = 0;
263 if ( l != NULL )
264 {
265 gint32 dif = mix_word_magnitude (x) - mix_word_magnitude (y);
266 if ( dif < 0)
267 *l = (-dif)|mix_word_sign (y);
268 else
269 *l = dif|mix_word_sign (x);
270 }
271 }
272
273 return result;
274 }
275
276
277 void
mix_word_mul(mix_word_t x,mix_word_t y,mix_word_t * high_word,mix_word_t * low_word)278 mix_word_mul (mix_word_t x, mix_word_t y,
279 mix_word_t *high_word, mix_word_t *low_word)
280 {
281 guint32 sign = mix_word_sign (x) ^ mix_word_sign (y);
282
283 /*
284 x = x0 + x1 * 2 ^ 10 + x2 * 2 ^ 20
285 y = y0 + y1 * 2 ^ 10 + y2 * 2 ^ 20
286 x0, x1, x2, y0, y1, y2 are < 2 ^ 10
287 */
288 guint32 x0 = (x & 0x000003FF);
289 guint32 x1 = (x & 0x000FFC00) >> 10;
290 guint32 x2 = (x & 0x3FF00000) >> 20;
291 guint32 y0 = (y & 0x000003FF);
292 guint32 y1 = (y & 0x000FFC00) >> 10;
293 guint32 y2 = (y & 0x3FF00000) >> 20;
294
295 /*
296 x * y = partial0 +
297 partial1 * 2 ^ 10 +
298 partial2 * 2 ^ 20 +
299 partial3 * 2 ^ 30 +
300 partial4 * 2 ^ 40
301 partial0 and partial4 are < 2 ^ 20
302 partial1 and partial3 are < 2 ^ 21
303 partial2 is < 3 * 2 ^ 20
304 */
305 guint32 partial0 = x0 * y0;
306 guint32 partial1 = x0 * y1 + x1 * y0;
307 guint32 partial2 = x0 * y2 + x1 * y1 + x2 * y0;
308 guint32 partial3 = x1 * y2 + x2 * y1;
309 guint32 partial4 = x2 * y2;
310
311 /* sum1 has a place value of 1 and is < 2 ^ 32 */
312 guint32 sum1 = partial0 + (partial1 << 10);
313 guint32 carry1 = (sum1 & 0xFFF00000) >> 20;
314
315 /* sum2 has a place value of 2 ^ 20 and is < 2 ^ 32 */
316 guint32 sum2 = partial2 + (partial3 << 10) + carry1;
317 guint32 carry2 = (sum2 & 0xFFF00000) >> 20;
318
319 /* sum3 has a place value of 2 ^ 40 and is < 2 ^ 20 */
320 guint32 sum3 = partial4 + carry2;
321
322 sum1 &= ~0xFFF00000;
323 sum2 &= ~0xFFF00000;
324
325 /*
326 Now paste the three values back into two.
327 */
328 if ( low_word != NULL ) {
329 *low_word = sum1 | ((sum2 & 0x000003FF) << 20);
330 *low_word |= sign;
331 }
332 if ( high_word != NULL ) {
333 *high_word = ((sum2 & 0x000FFC00) >> 10) | (sum3 << 10);
334 *high_word |= sign;
335 }
336 }
337
338
339 gboolean
mix_word_div(mix_word_t n1,mix_word_t n0,mix_word_t d,mix_word_t * quotient,mix_word_t * remainder)340 mix_word_div (mix_word_t n1, mix_word_t n0, mix_word_t d,
341 mix_word_t *quotient, mix_word_t *remainder)
342 {
343 gboolean overflow = FALSE;
344 long magn1 = mix_word_magnitude (n1);
345 long magd = mix_word_magnitude (d);
346
347 if (magd == 0)
348 {
349 overflow = TRUE;
350 /* just so they have -some- valid value */
351 if ( quotient != NULL ) *quotient = 0;
352 if ( remainder != NULL ) *remainder = 0;
353 }
354 else if (magn1 == 0)
355 { /* special-cased for speed */
356 if ( quotient != NULL )
357 *quotient = (mix_word_sign (n1) ^ mix_word_sign (d))
358 | (mix_word_magnitude (n0) / magd);
359 if ( remainder != NULL )
360 *remainder = mix_word_sign (n1) | (mix_word_magnitude (n0) % magd);
361 }
362 else if (magd <= magn1)
363 {
364 overflow = TRUE;
365 if ( quotient != NULL ) *quotient = 0;
366 if ( remainder != NULL ) *remainder = 0;
367 }
368 else
369 {
370 long q = mix_word_magnitude (n0);
371 long r = magn1;
372 unsigned i;
373 for (i = 30; i != 0; --i) {
374 r <<= 1;
375 if ( (q & (1L << 29)) != 0 )
376 ++r;
377 q = (q << 1) & ((1L << 30) - 1);
378 if (magd <= r)
379 ++q, r -= magd;
380 }
381 if ( quotient != NULL )
382 *quotient = (mix_word_sign (n1) ^ mix_word_sign (d)) | q;
383 if ( remainder != NULL )
384 *remainder = mix_word_sign(n1) | r;
385 }
386 return overflow;
387 }
388
389 void
mix_word_shift_right(mix_word_t A,mix_word_t X,gulong count,mix_word_t * pA,mix_word_t * pX)390 mix_word_shift_right (mix_word_t A, mix_word_t X, gulong count,
391 mix_word_t *pA, mix_word_t *pX)
392 {
393 if ( pX != NULL ) *pX = mix_word_sign (X);
394 if ( pA != NULL ) *pA = mix_word_sign (A);
395 if (count < 5) {
396 if ( pA != NULL )
397 *pA |= mix_word_magnitude (A) >> (6 * count);
398 if ( pX != NULL )
399 *pX |= MIX_WORD_MAX & ( (mix_word_magnitude (X) >> (6 * count))
400 | (A << (30 - 6 * count)) );
401 } else if (count < 10 && pX != NULL)
402 *pX |= mix_word_magnitude (A) >> (6 * count - 30);
403 else
404 ;
405 }
406
407
408 void
mix_word_shift_left(mix_word_t A,mix_word_t X,gulong count,mix_word_t * pA,mix_word_t * pX)409 mix_word_shift_left (mix_word_t A, mix_word_t X, gulong count,
410 mix_word_t *pA, mix_word_t *pX)
411 {
412 if ( pX != NULL ) *pX = mix_word_sign (X);
413 if ( pA != NULL ) *pA = mix_word_sign (A);
414 if (count < 5) {
415 if ( pX != NULL ) *pX |= MIX_WORD_MAX & (X << (6 * count));
416 if ( pA != NULL )
417 *pA |= MIX_WORD_MAX & ( (A << (6 * count)) |
418 (mix_word_magnitude (X) >> (30 - 6 * count)) );
419 } else if (count < 10 && pA != NULL)
420 *pA |= MIX_WORD_MAX & (X << (6 * count - 30));
421 else
422 ;
423 }
424
425 void
mix_word_shift_left_circular(mix_word_t A,mix_word_t X,gulong count,mix_word_t * pA,mix_word_t * pX)426 mix_word_shift_left_circular (mix_word_t A, mix_word_t X, gulong count,
427 mix_word_t *pA, mix_word_t *pX)
428 {
429 mix_word_t A1, X1;
430 guint c;
431
432 count %= 10;
433 A1 = count < 5 ? A : X;
434 X1 = count < 5 ? X : A;
435 c = 6 * (count < 5 ? count : count - 5);
436 if ( pX != NULL )
437 *pX = mix_word_sign (X)
438 | ( MIX_WORD_MAX & (X1 << c) ) | ( mix_word_magnitude (A1) >> (30 - c) );
439 if ( pA != NULL )
440 *pA = mix_word_sign (A)
441 | ( MIX_WORD_MAX & (A1 << c) ) | ( mix_word_magnitude (X1) >> (30 - c) );
442 }
443
444 void
mix_word_shift_right_circular(mix_word_t A,mix_word_t X,gulong count,mix_word_t * pA,mix_word_t * pX)445 mix_word_shift_right_circular (mix_word_t A, mix_word_t X, gulong count,
446 mix_word_t *pA, mix_word_t *pX)
447 {
448 mix_word_t A1, X1;
449 guint c;
450
451 count %= 10;
452 A1 = count < 5 ? A : X;
453 X1 = count < 5 ? X : A;
454 c = 6 * (count < 5 ? count : count - 5);
455 if ( pX != NULL )
456 *pX = mix_word_sign (X)
457 | ( mix_word_magnitude (X1) >> c ) | ( MIX_WORD_MAX & (A1 << (30 - c)) );
458 if ( pA != NULL )
459 *pA = mix_word_sign (A)
460 | ( mix_word_magnitude (A1) >> c ) | ( MIX_WORD_MAX & (X1 << (30 - c)) );
461 }
462
463 void
mix_word_shift_left_binary(mix_word_t A,mix_word_t X,gulong count,mix_word_t * pA,mix_word_t * pX)464 mix_word_shift_left_binary (mix_word_t A, mix_word_t X, gulong count,
465 mix_word_t *pA, mix_word_t *pX)
466 {
467 if ( pX != NULL ) *pX = mix_word_sign (X);
468 if ( pA != NULL ) *pA = mix_word_sign (A);
469 if (count < 30) {
470 if ( pX != NULL ) *pX |= MIX_WORD_MAX & (X << count);
471 if ( pA != NULL )
472 *pA |= MIX_WORD_MAX & ( (A << count) |
473 (mix_word_magnitude (X) >> (30 - count)) );
474 } else if (count < 60 && pA != NULL)
475 *pA |= MIX_WORD_MAX & (X << (count - 30));
476 else
477 ;
478 }
479
480 void
mix_word_shift_right_binary(mix_word_t A,mix_word_t X,gulong count,mix_word_t * pA,mix_word_t * pX)481 mix_word_shift_right_binary (mix_word_t A, mix_word_t X, gulong count,
482 mix_word_t *pA, mix_word_t *pX)
483 {
484 if ( pX != NULL ) *pX = mix_word_sign (X);
485 if ( pA != NULL ) *pA = mix_word_sign (A);
486 if (count < 30) {
487 if ( pA != NULL )
488 *pA |= mix_word_magnitude (A) >> count;
489 if ( pX != NULL )
490 *pX |= MIX_WORD_MAX & ( (mix_word_magnitude (X) >> count)
491 | (A << (30 - count)) );
492 } else if (count < 60 && pX != NULL)
493 *pX |= mix_word_magnitude (A) >> (count - 30);
494 else
495 ;
496 }
497
498 /* Printable representation */
499 void
mix_word_print_to_file(mix_word_t word,const char * message,FILE * f)500 mix_word_print_to_file (mix_word_t word, const char *message, FILE *f)
501 {
502 guint k;
503 if ( message ) fprintf (f, "%s ", message);
504 fprintf (f, "%s ", mix_word_sign (word) == 0 ? "+" : "-");
505 for ( k = 1; k < 6; ++k ) {
506 fprintf (f, "%02d ", mix_word_get_byte (word,k));
507 }
508 fprintf (f, "(%010ld)", mix_word_magnitude (word));
509 }
510
511 void
mix_word_print_to_buffer(mix_word_t word,gchar * buf)512 mix_word_print_to_buffer (mix_word_t word, gchar *buf)
513 {
514 g_return_if_fail (buf != NULL);
515 sprintf (buf, "%s %02d %02d %02d %02d %02d",
516 mix_word_sign (word) == 0 ? "+" : "-",
517 mix_word_get_byte (word, 1),
518 mix_word_get_byte (word, 2),
519 mix_word_get_byte (word, 3),
520 mix_word_get_byte (word, 4),
521 mix_word_get_byte (word, 5));
522 }
523
524 /* Conversions between words and shorts */
525 mix_short_t
mix_word_to_short(mix_word_t word)526 mix_word_to_short (mix_word_t word)
527 {
528 if ( mix_word_is_negative (word) )
529 return ( (word & MIX_SHORT_MAX) | MIX_SHORT_SIGN_BIT );
530 else
531 return (word & MIX_SHORT_MAX);
532 }
533
534 mix_word_t
mix_short_to_word(mix_short_t s)535 mix_short_to_word (mix_short_t s)
536 {
537 if ( mix_short_is_negative (s) )
538 return ((mix_word_t) (mix_short_magnitude (s) | MIX_WORD_SIGN_BIT));
539 else
540 return ((mix_word_t)s);
541 }
542
543 mix_short_t
mix_short_add(mix_short_t x,mix_short_t y)544 mix_short_add (mix_short_t x, mix_short_t y)
545 {
546 static const guint16 MIX_SHORT_MAX_SIM = 2*MIX_SHORT_MAX + 1;
547
548 gint16 result;
549 if ( mix_short_sign (x) == mix_short_sign (y) )
550 {
551 result = (mix_short_magnitude (x) + mix_short_magnitude (y));
552 if ( result > MIX_SHORT_MAX ) {
553 /* for instance MIX_SHORT_MAX + 1 = - MIX_SHORT_MAX */
554 result = MIX_SHORT_MAX_SIM - result;
555 result |= mix_short_sign (mix_short_negative (x));
556 } else if ( result != 0 )
557 result |= mix_short_sign (x);
558 /* keep positive sign for 0 so that w - w == -w + w */
559 }
560 else
561 {
562 result = mix_short_magnitude (x) - mix_short_magnitude (y);
563 if (result < 0)
564 result = -result|mix_short_sign (y);
565 else if (result > 0)
566 result = result|mix_short_sign (x);
567 /* keep positive sign for 0 so that w - w == -w + w */
568 }
569
570 g_assert ( result >= 0 );
571
572 return (mix_short_t)result;
573 }
574
575
576 /* Printable representation */
577 void
mix_short_print(mix_short_t s,const gchar * message)578 mix_short_print (mix_short_t s, const gchar *message)
579 {
580 if ( message ) g_print ("%s ", message);
581 g_print ("%s ", mix_short_sign (s) == 0 ? "+" : "-");
582 g_print ("%02d %02d ", mix_byte_new (s>>6), mix_byte_new (s));
583 g_print ("(%04d)", mix_short_magnitude (s));
584 }
585
586 void
mix_short_print_to_buffer(mix_short_t s,gchar * buf)587 mix_short_print_to_buffer (mix_short_t s, gchar *buf)
588 {
589 g_return_if_fail (buf != NULL);
590 sprintf (buf, "%s %02d %02d",
591 mix_short_sign (s) == 0 ? "+" : "-",
592 mix_byte_new (s>>6), mix_byte_new (s));
593 /* g_print ("(%04d)", mix_short_magnitude (s));*/
594 }
595