H. Peter Anvin | bdc8078 | 2008-02-08 04:21:26 -0800 | [diff] [blame] | 1 | #!/usr/bin/perl |
| 2 | # ----------------------------------------------------------------------- |
| 3 | # |
| 4 | # Copyright 2007 rPath, Inc. - All Rights Reserved |
| 5 | # |
| 6 | # This file is part of the Linux kernel, and is made available under |
| 7 | # the terms of the GNU General Public License version 2 or (at your |
| 8 | # option) any later version; incorporated herein by reference. |
| 9 | # |
| 10 | # ----------------------------------------------------------------------- |
| 11 | # |
| 12 | |
| 13 | # |
| 14 | # Usage: timeconst.pl HZ > timeconst.h |
| 15 | # |
| 16 | |
| 17 | # Precomputed values for systems without Math::BigInt |
| 18 | # Generated by: |
| 19 | # timeconst.pl --can 24 32 48 64 100 122 128 200 250 256 300 512 1000 1024 1200 |
| 20 | %canned_values = ( |
| 21 | 24 => [ |
| 22 | '0xa6aaaaab','0x2aaaaaa',26, |
| 23 | '0xa6aaaaaaaaaaaaab','0x2aaaaaaaaaaaaaa',58, |
| 24 | 125,3, |
| 25 | '0xc49ba5e4','0x1fbe76c8b4',37, |
| 26 | '0xc49ba5e353f7ceda','0x1fbe76c8b439581062',69, |
| 27 | 3,125, |
| 28 | '0xa2c2aaab','0xaaaa',16, |
| 29 | '0xa2c2aaaaaaaaaaab','0xaaaaaaaaaaaa',48, |
| 30 | 125000,3, |
| 31 | '0xc9539b89','0x7fffbce4217d',47, |
| 32 | '0xc9539b8887229e91','0x7fffbce4217d2849cb25',79, |
| 33 | 3,125000, |
| 34 | ], 32 => [ |
| 35 | '0xfa000000','0x6000000',27, |
| 36 | '0xfa00000000000000','0x600000000000000',59, |
| 37 | 125,4, |
| 38 | '0x83126e98','0xfdf3b645a',36, |
| 39 | '0x83126e978d4fdf3c','0xfdf3b645a1cac0831',68, |
| 40 | 4,125, |
| 41 | '0xf4240000','0x0',17, |
| 42 | '0xf424000000000000','0x0',49, |
| 43 | 31250,1, |
| 44 | '0x8637bd06','0x3fff79c842fa',46, |
| 45 | '0x8637bd05af6c69b6','0x3fff79c842fa5093964a',78, |
| 46 | 1,31250, |
| 47 | ], 48 => [ |
| 48 | '0xa6aaaaab','0x6aaaaaa',27, |
| 49 | '0xa6aaaaaaaaaaaaab','0x6aaaaaaaaaaaaaa',59, |
| 50 | 125,6, |
| 51 | '0xc49ba5e4','0xfdf3b645a',36, |
| 52 | '0xc49ba5e353f7ceda','0xfdf3b645a1cac0831',68, |
| 53 | 6,125, |
| 54 | '0xa2c2aaab','0x15555',17, |
| 55 | '0xa2c2aaaaaaaaaaab','0x1555555555555',49, |
| 56 | 62500,3, |
| 57 | '0xc9539b89','0x3fffbce4217d',46, |
| 58 | '0xc9539b8887229e91','0x3fffbce4217d2849cb25',78, |
| 59 | 3,62500, |
| 60 | ], 64 => [ |
| 61 | '0xfa000000','0xe000000',28, |
| 62 | '0xfa00000000000000','0xe00000000000000',60, |
| 63 | 125,8, |
| 64 | '0x83126e98','0x7ef9db22d',35, |
| 65 | '0x83126e978d4fdf3c','0x7ef9db22d0e560418',67, |
| 66 | 8,125, |
| 67 | '0xf4240000','0x0',18, |
| 68 | '0xf424000000000000','0x0',50, |
| 69 | 15625,1, |
| 70 | '0x8637bd06','0x1fff79c842fa',45, |
| 71 | '0x8637bd05af6c69b6','0x1fff79c842fa5093964a',77, |
| 72 | 1,15625, |
| 73 | ], 100 => [ |
| 74 | '0xa0000000','0x0',28, |
| 75 | '0xa000000000000000','0x0',60, |
| 76 | 10,1, |
| 77 | '0xcccccccd','0x733333333',35, |
| 78 | '0xcccccccccccccccd','0x73333333333333333',67, |
| 79 | 1,10, |
| 80 | '0x9c400000','0x0',18, |
| 81 | '0x9c40000000000000','0x0',50, |
| 82 | 10000,1, |
| 83 | '0xd1b71759','0x1fff2e48e8a7',45, |
| 84 | '0xd1b71758e219652c','0x1fff2e48e8a71de69ad4',77, |
| 85 | 1,10000, |
| 86 | ], 122 => [ |
| 87 | '0x8325c53f','0xfbcda3a',28, |
| 88 | '0x8325c53ef368eb05','0xfbcda3ac10c9714',60, |
| 89 | 500,61, |
| 90 | '0xf9db22d1','0x7fbe76c8b',35, |
| 91 | '0xf9db22d0e560418a','0x7fbe76c8b43958106',67, |
| 92 | 61,500, |
| 93 | '0x8012e2a0','0x3ef36',18, |
| 94 | '0x8012e29f79b47583','0x3ef368eb04325',50, |
| 95 | 500000,61, |
| 96 | '0xffda4053','0x1ffffbce4217',45, |
| 97 | '0xffda4052d666a983','0x1ffffbce4217d2849cb2',77, |
| 98 | 61,500000, |
| 99 | ], 128 => [ |
| 100 | '0xfa000000','0x1e000000',29, |
| 101 | '0xfa00000000000000','0x1e00000000000000',61, |
| 102 | 125,16, |
| 103 | '0x83126e98','0x3f7ced916',34, |
| 104 | '0x83126e978d4fdf3c','0x3f7ced916872b020c',66, |
| 105 | 16,125, |
| 106 | '0xf4240000','0x40000',19, |
| 107 | '0xf424000000000000','0x4000000000000',51, |
| 108 | 15625,2, |
| 109 | '0x8637bd06','0xfffbce4217d',44, |
| 110 | '0x8637bd05af6c69b6','0xfffbce4217d2849cb25',76, |
| 111 | 2,15625, |
| 112 | ], 200 => [ |
| 113 | '0xa0000000','0x0',29, |
| 114 | '0xa000000000000000','0x0',61, |
| 115 | 5,1, |
| 116 | '0xcccccccd','0x333333333',34, |
| 117 | '0xcccccccccccccccd','0x33333333333333333',66, |
| 118 | 1,5, |
| 119 | '0x9c400000','0x0',19, |
| 120 | '0x9c40000000000000','0x0',51, |
| 121 | 5000,1, |
| 122 | '0xd1b71759','0xfff2e48e8a7',44, |
| 123 | '0xd1b71758e219652c','0xfff2e48e8a71de69ad4',76, |
| 124 | 1,5000, |
| 125 | ], 250 => [ |
| 126 | '0x80000000','0x0',29, |
| 127 | '0x8000000000000000','0x0',61, |
| 128 | 4,1, |
| 129 | '0x80000000','0x180000000',33, |
| 130 | '0x8000000000000000','0x18000000000000000',65, |
| 131 | 1,4, |
| 132 | '0xfa000000','0x0',20, |
| 133 | '0xfa00000000000000','0x0',52, |
| 134 | 4000,1, |
| 135 | '0x83126e98','0x7ff7ced9168',43, |
| 136 | '0x83126e978d4fdf3c','0x7ff7ced916872b020c4',75, |
| 137 | 1,4000, |
| 138 | ], 256 => [ |
| 139 | '0xfa000000','0x3e000000',30, |
| 140 | '0xfa00000000000000','0x3e00000000000000',62, |
| 141 | 125,32, |
| 142 | '0x83126e98','0x1fbe76c8b',33, |
| 143 | '0x83126e978d4fdf3c','0x1fbe76c8b43958106',65, |
| 144 | 32,125, |
| 145 | '0xf4240000','0xc0000',20, |
| 146 | '0xf424000000000000','0xc000000000000',52, |
| 147 | 15625,4, |
| 148 | '0x8637bd06','0x7ffde7210be',43, |
| 149 | '0x8637bd05af6c69b6','0x7ffde7210be9424e592',75, |
| 150 | 4,15625, |
| 151 | ], 300 => [ |
| 152 | '0xd5555556','0x2aaaaaaa',30, |
| 153 | '0xd555555555555556','0x2aaaaaaaaaaaaaaa',62, |
| 154 | 10,3, |
| 155 | '0x9999999a','0x1cccccccc',33, |
| 156 | '0x999999999999999a','0x1cccccccccccccccc',65, |
| 157 | 3,10, |
| 158 | '0xd0555556','0xaaaaa',20, |
| 159 | '0xd055555555555556','0xaaaaaaaaaaaaa',52, |
| 160 | 10000,3, |
| 161 | '0x9d495183','0x7ffcb923a29',43, |
| 162 | '0x9d495182a9930be1','0x7ffcb923a29c779a6b5',75, |
| 163 | 3,10000, |
| 164 | ], 512 => [ |
| 165 | '0xfa000000','0x7e000000',31, |
| 166 | '0xfa00000000000000','0x7e00000000000000',63, |
| 167 | 125,64, |
| 168 | '0x83126e98','0xfdf3b645',32, |
| 169 | '0x83126e978d4fdf3c','0xfdf3b645a1cac083',64, |
| 170 | 64,125, |
| 171 | '0xf4240000','0x1c0000',21, |
| 172 | '0xf424000000000000','0x1c000000000000',53, |
| 173 | 15625,8, |
| 174 | '0x8637bd06','0x3ffef39085f',42, |
| 175 | '0x8637bd05af6c69b6','0x3ffef39085f4a1272c9',74, |
| 176 | 8,15625, |
| 177 | ], 1000 => [ |
| 178 | '0x80000000','0x0',31, |
| 179 | '0x8000000000000000','0x0',63, |
| 180 | 1,1, |
| 181 | '0x80000000','0x0',31, |
| 182 | '0x8000000000000000','0x0',63, |
| 183 | 1,1, |
| 184 | '0xfa000000','0x0',22, |
| 185 | '0xfa00000000000000','0x0',54, |
| 186 | 1000,1, |
| 187 | '0x83126e98','0x1ff7ced9168',41, |
| 188 | '0x83126e978d4fdf3c','0x1ff7ced916872b020c4',73, |
| 189 | 1,1000, |
| 190 | ], 1024 => [ |
| 191 | '0xfa000000','0xfe000000',32, |
| 192 | '0xfa00000000000000','0xfe00000000000000',64, |
| 193 | 125,128, |
| 194 | '0x83126e98','0x7ef9db22',31, |
| 195 | '0x83126e978d4fdf3c','0x7ef9db22d0e56041',63, |
| 196 | 128,125, |
| 197 | '0xf4240000','0x3c0000',22, |
| 198 | '0xf424000000000000','0x3c000000000000',54, |
| 199 | 15625,16, |
| 200 | '0x8637bd06','0x1fff79c842f',41, |
| 201 | '0x8637bd05af6c69b6','0x1fff79c842fa5093964',73, |
| 202 | 16,15625, |
| 203 | ], 1200 => [ |
| 204 | '0xd5555556','0xd5555555',32, |
| 205 | '0xd555555555555556','0xd555555555555555',64, |
| 206 | 5,6, |
| 207 | '0x9999999a','0x66666666',31, |
| 208 | '0x999999999999999a','0x6666666666666666',63, |
| 209 | 6,5, |
| 210 | '0xd0555556','0x2aaaaa',22, |
| 211 | '0xd055555555555556','0x2aaaaaaaaaaaaa',54, |
| 212 | 2500,3, |
| 213 | '0x9d495183','0x1ffcb923a29',41, |
| 214 | '0x9d495182a9930be1','0x1ffcb923a29c779a6b5',73, |
| 215 | 3,2500, |
| 216 | ] |
| 217 | ); |
| 218 | |
| 219 | $has_bigint = eval 'use Math::BigInt qw(bgcd); 1;'; |
| 220 | |
| 221 | sub bint($) |
| 222 | { |
| 223 | my($x) = @_; |
| 224 | return Math::BigInt->new($x); |
| 225 | } |
| 226 | |
| 227 | # |
| 228 | # Constants for division by reciprocal multiplication. |
| 229 | # (bits, numerator, denominator) |
| 230 | # |
| 231 | sub fmul($$$) |
| 232 | { |
| 233 | my ($b,$n,$d) = @_; |
| 234 | |
| 235 | $n = bint($n); |
| 236 | $d = bint($d); |
| 237 | |
| 238 | return scalar (($n << $b)+$d-bint(1))/$d; |
| 239 | } |
| 240 | |
| 241 | sub fadj($$$) |
| 242 | { |
| 243 | my($b,$n,$d) = @_; |
| 244 | |
| 245 | $n = bint($n); |
| 246 | $d = bint($d); |
| 247 | |
| 248 | $d = $d/bgcd($n, $d); |
| 249 | return scalar (($d-bint(1)) << $b)/$d; |
| 250 | } |
| 251 | |
| 252 | sub fmuls($$$) { |
| 253 | my($b,$n,$d) = @_; |
| 254 | my($s,$m); |
| 255 | my($thres) = bint(1) << ($b-1); |
| 256 | |
| 257 | $n = bint($n); |
| 258 | $d = bint($d); |
| 259 | |
| 260 | for ($s = 0; 1; $s++) { |
| 261 | $m = fmul($s,$n,$d); |
| 262 | return $s if ($m >= $thres); |
| 263 | } |
| 264 | return 0; |
| 265 | } |
| 266 | |
| 267 | # Provides mul, adj, and shr factors for a specific |
| 268 | # (bit, time, hz) combination |
| 269 | sub muladj($$$) { |
| 270 | my($b, $t, $hz) = @_; |
| 271 | my $s = fmuls($b, $t, $hz); |
| 272 | my $m = fmul($s, $t, $hz); |
| 273 | my $a = fadj($s, $t, $hz); |
| 274 | return ($m->as_hex(), $a->as_hex(), $s); |
| 275 | } |
| 276 | |
| 277 | # Provides numerator, denominator values |
| 278 | sub numden($$) { |
| 279 | my($n, $d) = @_; |
| 280 | my $g = bgcd($n, $d); |
| 281 | return ($n/$g, $d/$g); |
| 282 | } |
| 283 | |
| 284 | # All values for a specific (time, hz) combo |
| 285 | sub conversions($$) { |
| 286 | my ($t, $hz) = @_; |
| 287 | my @val = (); |
| 288 | |
| 289 | # HZ_TO_xx |
| 290 | push(@val, muladj(32, $t, $hz)); |
| 291 | push(@val, muladj(64, $t, $hz)); |
| 292 | push(@val, numden($t, $hz)); |
| 293 | |
| 294 | # xx_TO_HZ |
| 295 | push(@val, muladj(32, $hz, $t)); |
| 296 | push(@val, muladj(64, $hz, $t)); |
| 297 | push(@val, numden($hz, $t)); |
| 298 | |
| 299 | return @val; |
| 300 | } |
| 301 | |
| 302 | sub compute_values($) { |
| 303 | my($hz) = @_; |
| 304 | my @val = (); |
| 305 | my $s, $m, $a, $g; |
| 306 | |
| 307 | if (!$has_bigint) { |
| 308 | die "$0: HZ == $hz not canned and ". |
| 309 | "Math::BigInt not available\n"; |
| 310 | } |
| 311 | |
| 312 | # MSEC conversions |
| 313 | push(@val, conversions(1000, $hz)); |
| 314 | |
| 315 | # USEC conversions |
| 316 | push(@val, conversions(1000000, $hz)); |
| 317 | |
| 318 | return @val; |
| 319 | } |
| 320 | |
| 321 | sub output($@) |
| 322 | { |
| 323 | my($hz, @val) = @_; |
| 324 | my $pfx, $bit, $suf, $s, $m, $a; |
| 325 | |
| 326 | print "/* Automatically generated by kernel/timeconst.pl */\n"; |
| 327 | print "/* Conversion constants for HZ == $hz */\n"; |
| 328 | print "\n"; |
| 329 | print "#ifndef KERNEL_TIMECONST_H\n"; |
| 330 | print "#define KERNEL_TIMECONST_H\n"; |
| 331 | print "\n"; |
| 332 | |
| 333 | print "#include <linux/param.h>\n"; |
| 334 | |
| 335 | print "\n"; |
| 336 | print "#if HZ != $hz\n"; |
| 337 | print "#error \"kernel/timeconst.h has the wrong HZ value!\"\n"; |
| 338 | print "#endif\n"; |
| 339 | print "\n"; |
| 340 | |
| 341 | foreach $pfx ('HZ_TO_MSEC','MSEC_TO_HZ', |
H. Peter Anvin | c98aa86 | 2008-02-12 13:52:37 -0800 | [diff] [blame] | 342 | 'HZ_TO_USEC','USEC_TO_HZ') { |
H. Peter Anvin | bdc8078 | 2008-02-08 04:21:26 -0800 | [diff] [blame] | 343 | foreach $bit (32, 64) { |
| 344 | foreach $suf ('MUL', 'ADJ', 'SHR') { |
| 345 | printf "#define %-23s %s\n", |
| 346 | "${pfx}_$suf$bit", shift(@val); |
| 347 | } |
| 348 | } |
| 349 | foreach $suf ('NUM', 'DEN') { |
| 350 | printf "#define %-23s %s\n", |
| 351 | "${pfx}_$suf", shift(@val); |
| 352 | } |
| 353 | } |
| 354 | |
| 355 | print "\n"; |
| 356 | print "#endif /* KERNEL_TIMECONST_H */\n"; |
| 357 | } |
| 358 | |
| 359 | ($hz) = @ARGV; |
| 360 | |
| 361 | # Use this to generate the %canned_values structure |
| 362 | if ($hz eq '--can') { |
| 363 | shift(@ARGV); |
| 364 | @hzlist = sort {$a <=> $b} (@ARGV); |
| 365 | |
| 366 | print "# Precomputed values for systems without Math::BigInt\n"; |
| 367 | print "# Generated by:\n"; |
| 368 | print "# timeconst.pl --can ", join(' ', @hzlist), "\n"; |
| 369 | print "\%canned_values = (\n"; |
| 370 | my $pf = "\t"; |
| 371 | foreach $hz (@hzlist) { |
| 372 | my @values = compute_values($hz); |
| 373 | print "$pf$hz => [\n"; |
| 374 | while (scalar(@values)) { |
| 375 | my $bit; |
| 376 | foreach $bit (32, 64) { |
| 377 | my $m = shift(@values); |
| 378 | my $a = shift(@values); |
| 379 | my $s = shift(@values); |
| 380 | print "\t\t\'",$m,"\',\'",$a,"\',",$s,",\n"; |
| 381 | } |
| 382 | my $n = shift(@values); |
| 383 | my $d = shift(@values); |
| 384 | print "\t\t",$n,',',$d,",\n"; |
| 385 | } |
| 386 | print "\t]"; |
| 387 | $pf = ', '; |
| 388 | } |
| 389 | print "\n);\n"; |
| 390 | } else { |
| 391 | $hz += 0; # Force to number |
| 392 | if ($hz < 1) { |
| 393 | die "Usage: $0 HZ\n"; |
| 394 | } |
| 395 | |
| 396 | @val = @{$canned_values{$hz}}; |
| 397 | if (!defined(@val)) { |
| 398 | @val = compute_values($hz); |
| 399 | } |
| 400 | output($hz, @val); |
| 401 | } |
| 402 | exit 0; |