1 | /*****************************************************************************/ |
2 | /* */ |
3 | /* alignment.c */ |
4 | /* */ |
5 | /* Address aligment */ |
6 | /* */ |
7 | /* */ |
8 | /* */ |
9 | /* (C) 2011, Ullrich von Bassewitz */ |
10 | /* Roemerstrasse 52 */ |
11 | /* 70794 Filderstadt */ |
12 | /* EMail: uz@cc65.org */ |
13 | /* */ |
14 | /* */ |
15 | /* This software is provided 'as-is', without any expressed or implied */ |
16 | /* warranty. In no event will the authors be held liable for any damages */ |
17 | /* arising from the use of this software. */ |
18 | /* */ |
19 | /* Permission is granted to anyone to use this software for any purpose, */ |
20 | /* including commercial applications, and to alter it and redistribute it */ |
21 | /* freely, subject to the following restrictions: */ |
22 | /* */ |
23 | /* 1. The origin of this software must not be misrepresented; you must not */ |
24 | /* claim that you wrote the original software. If you use this software */ |
25 | /* in a product, an acknowledgment in the product documentation would be */ |
26 | /* appreciated but is not required. */ |
27 | /* 2. Altered source versions must be plainly marked as such, and must not */ |
28 | /* be misrepresented as being the original software. */ |
29 | /* 3. This notice may not be removed or altered from any source */ |
30 | /* distribution. */ |
31 | /* */ |
32 | /*****************************************************************************/ |
33 | |
34 | |
35 | |
36 | /* common */ |
37 | #include "alignment.h" |
38 | #include "check.h" |
39 | |
40 | |
41 | |
42 | /*****************************************************************************/ |
43 | /* Data */ |
44 | /*****************************************************************************/ |
45 | |
46 | |
47 | |
48 | /* To factorize an alignment, we will use the following prime table. It lists |
49 | ** all primes up to 256, which means we're able to factorize alignments up to |
50 | ** 0x10000. This is checked in the code. |
51 | */ |
52 | static const unsigned char Primes[] = { |
53 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, |
54 | 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, |
55 | 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, |
56 | 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, |
57 | 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, |
58 | 233, 239, 241, 251 |
59 | }; |
60 | #define PRIME_COUNT (sizeof (Primes) / sizeof (Primes[0])) |
61 | #define LAST_PRIME ((unsigned long)Primes[PRIME_COUNT-1]) |
62 | |
63 | |
64 | |
65 | /* A number together with its prime factors */ |
66 | typedef struct FactorizedNumber FactorizedNumber; |
67 | struct FactorizedNumber { |
68 | unsigned long Value; /* The actual number */ |
69 | unsigned long Remainder; /* Remaining prime */ |
70 | unsigned char Powers[PRIME_COUNT]; /* Powers of the factors */ |
71 | }; |
72 | |
73 | |
74 | |
75 | /*****************************************************************************/ |
76 | /* Code */ |
77 | /*****************************************************************************/ |
78 | |
79 | |
80 | |
81 | static void Initialize (FactorizedNumber* F, unsigned long Value) |
82 | /* Initialize a FactorizedNumber structure */ |
83 | { |
84 | unsigned I; |
85 | |
86 | F->Value = Value; |
87 | F->Remainder = 1; |
88 | for (I = 0; I < PRIME_COUNT; ++I) { |
89 | F->Powers[I] = 0; |
90 | } |
91 | } |
92 | |
93 | |
94 | |
95 | static void Factorize (unsigned long Value, FactorizedNumber* F) |
96 | /* Factorize a value between 1 and 0x10000 that is in F */ |
97 | { |
98 | unsigned I; |
99 | |
100 | /* Initialize F */ |
101 | Initialize (F, Value); |
102 | |
103 | /* If the value is 1 we're already done */ |
104 | if (Value == 1) { |
105 | return; |
106 | } |
107 | |
108 | /* Be sure we can factorize */ |
109 | CHECK (Value <= MAX_ALIGNMENT && Value != 0); |
110 | |
111 | /* Handle factor 2 separately for speed */ |
112 | while ((Value & 0x01UL) == 0UL) { |
113 | ++F->Powers[0]; |
114 | Value >>= 1; |
115 | } |
116 | |
117 | /* Factorize. */ |
118 | I = 1; /* Skip 2 because it was handled above */ |
119 | while (Value > 1) { |
120 | unsigned long Tmp = Value / Primes[I]; |
121 | if (Tmp * Primes[I] == Value) { |
122 | /* This is a factor */ |
123 | ++F->Powers[I]; |
124 | Value = Tmp; |
125 | } else { |
126 | /* This is not a factor, try next one */ |
127 | if (++I >= PRIME_COUNT) { |
128 | break; |
129 | } |
130 | } |
131 | } |
132 | |
133 | /* If something is left, it must be a remaining prime */ |
134 | F->Remainder = Value; |
135 | } |
136 | |
137 | |
138 | |
139 | unsigned long LeastCommonMultiple (unsigned long Left, unsigned long Right) |
140 | /* Calculate the least common multiple of two numbers and return |
141 | ** the result. |
142 | */ |
143 | { |
144 | unsigned I; |
145 | FactorizedNumber L, R; |
146 | unsigned long Res; |
147 | |
148 | /* Factorize the two numbers */ |
149 | Factorize (Left, &L); |
150 | Factorize (Right, &R); |
151 | |
152 | /* Generate the result from the factors. |
153 | ** Some thoughts on range problems: Since the largest numbers we can |
154 | ** factorize are 2^16 (0x10000), the only numbers that could produce an |
155 | ** overflow when using 32 bits are exactly these. But the LCM for 2^16 |
156 | ** and 2^16 is 2^16 so this will never happen and we're safe. |
157 | */ |
158 | Res = L.Remainder * R.Remainder; |
159 | for (I = 0; I < PRIME_COUNT; ++I) { |
160 | unsigned P = (L.Powers[I] > R.Powers[I])? L.Powers[I] : R.Powers[I]; |
161 | while (P--) { |
162 | Res *= Primes[I]; |
163 | } |
164 | } |
165 | |
166 | /* Return the calculated lcm */ |
167 | return Res; |
168 | } |
169 | |
170 | |
171 | |
172 | unsigned long AlignAddr (unsigned long Addr, unsigned long Alignment) |
173 | /* Align an address to the given alignment */ |
174 | { |
175 | return ((Addr + Alignment - 1) / Alignment) * Alignment; |
176 | } |
177 | |
178 | |
179 | |
180 | unsigned long AlignCount (unsigned long Addr, unsigned long Alignment) |
181 | /* Calculate how many bytes must be inserted to align Addr to Alignment */ |
182 | { |
183 | return AlignAddr (Addr, Alignment) - Addr; |
184 | } |
185 | |