~mdw / storin / blame
| Commit | Line | Data |
|---|---|---|
| e6e0e332 MW |
1 | /* -*-c-*- |
| 2 | * | |
| 3 | * $Id: arith24.c,v 1.1 2000/05/21 11:28:30 mdw Exp $ | |
| 4 | * | |
| 5 | * Arithmetic mod %$2^{24}$% | |
| 6 | * | |
| 7 | * (c) 2000 Mark Wooding | |
| 8 | */ | |
| 9 | ||
| 10 | /*----- Licensing notice --------------------------------------------------* | |
| 11 | * | |
| 12 | * Copyright (c) 2000 Mark Wooding | |
| 13 | * All rights reserved. | |
| 14 | * | |
| 15 | * Redistribution and use in source and binary forms, with or without | |
| 16 | * modification, are permitted provided that the following conditions are | |
| 17 | * met: | |
| 18 | * | |
| 19 | * 1. Redistributions of source code must retain the above copyright | |
| 20 | * notice, this list of conditions and the following disclaimer. | |
| 21 | * | |
| 22 | * 2, Redistributions in binary form must reproduce the above copyright | |
| 23 | * notice, this list of conditions and the following disclaimer in the | |
| 24 | * documentation and/or other materials provided with the distribution. | |
| 25 | * | |
| 26 | * 3. The name of the authors may not be used to endorse or promote | |
| 27 | * products derived from this software without specific prior written | |
| 28 | * permission. | |
| 29 | * | |
| 30 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED | |
| 31 | * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF | |
| 32 | * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN | |
| 33 | * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, | |
| 34 | * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
| 35 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |
| 36 | * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
| 37 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
| 38 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN | |
| 39 | * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
| 40 | * POSSIBILITY OF SUCH DAMAGE. | |
| 41 | * | |
| 42 | * Instead of accepting the above terms, you may redistribute and/or modify | |
| 43 | * this software under the terms of either the GNU General Public License, | |
| 44 | * or the GNU Library General Public License, published by the Free | |
| 45 | * Software Foundation; either version 2 of the License, or (at your | |
| 46 | * option) any later version. | |
| 47 | */ | |
| 48 | ||
| 49 | /*----- Revision history --------------------------------------------------* | |
| 50 | * | |
| 51 | * $Log: arith24.c,v $ | |
| 52 | * Revision 1.1 2000/05/21 11:28:30 mdw | |
| 53 | * Initial check-in. | |
| 54 | * | |
| 55 | */ | |
| 56 | ||
| 57 | /*----- Header files ------------------------------------------------------*/ | |
| 58 | ||
| 59 | #include "arith24.h" | |
| 60 | #include "bits.h" | |
| 61 | ||
| 62 | /*----- Main code ---------------------------------------------------------*/ | |
| 63 | ||
| 64 | /* --- @inv24@ --- * | |
| 65 | * | |
| 66 | * Arguments: @uint24 x@ = a number to invert | |
| 67 | * | |
| 68 | * Returns: The multiplicative inverse %$x^{-1}$% of %$x$% (mod | |
| 69 | * %$2^{24}$%, if %$x$% is odd, or zero if %$x$% is even (and | |
| 70 | * hence uninvertible). | |
| 71 | * | |
| 72 | * Use: Computes multiplicative inverses mod %$2^{24}$%. | |
| 73 | */ | |
| 74 | ||
| 75 | uint24 inv24(uint24 x) | |
| 76 | { | |
| 77 | uint32 m = MASK24 + 1; | |
| 78 | long a = 1, b = 0; | |
| 79 | uint32 n = x; | |
| 80 | ||
| 81 | for (;;) { | |
| 82 | uint32 q, r; | |
| 83 | long t; | |
| 84 | if (!(r = m % n)) | |
| 85 | break; | |
| 86 | q = m / n; | |
| 87 | m = n; n = r; | |
| 88 | t = a; a = b - q * a; b = t; | |
| 89 | } | |
| 90 | if (n != 1) | |
| 91 | return (0); | |
| 92 | return (U24(a)); | |
| 93 | } | |
| 94 | ||
| 95 | /*----- That's all, folks -------------------------------------------------*/ |