cleanup: Big pile of whitespace fixes, all at once.

[u/mdw/catacomb] / tests / mpx

diff --git a/tests/mpx b/tests/mpx
index 45f7705..e30e91a 100644 (file)
--- a/tests/mpx
+++ b/tests/mpx
@@ -1,6 +1,6 @@
 # Test vectors for low-level MP functions
 #
-# $Id: mpx,v 1.2 1999/11/14 13:53:12 mdw Exp $
+# $Id: mpx,v 1.12 2004/04/01 12:50:41 mdw Exp $
 
 # --- Load-store tests ---
 #
@@ -20,15 +20,42 @@ load-store {
   522f8b1de257972a25ec49c9ff56340e2684e847ef2fa4d5714d7c8d454e90f6;
 }
 
+# --- Two's complement tests ---
+
+2cb {
+  "" "";
+  00 00;
+  000000 00000000000000000000;
+  01 ff;
+  0123456789abcdef fedcba9876543211;
+  0123456789abcdef fffffffedcba9876543211;
+  0100000000 ffffff00000000;
+  00000000c1a4bc4b ffffffff3e5b43b5;
+  ffffffff3e5b43b5 00000000c1a4bc4b;
+}
+
+2cl {
+  "" "";
+  00 00;
+  000000 00000000000000000000;
+  01 ff;
+  efcdab8967452301 1132547698badcfe;
+  efcdab8967452301 1132547698badcfeffffffff;
+  0000000001 00000000ffffffff;
+  4bbca4c100000000 b5435b3effffffff;
+  b5435b3effffffff 4bbca4c100000000;
+}
+
 # --- Shift tests ---
 
 lsl {
-
   # --- Simple sanity checks ---
 
   01 2 04;
   01 4 10;
 
+  7 -1 0;
+
   # --- Copy shifts ---
 
   01 0 01;
@@ -107,12 +134,99 @@ lsl {
   0e0dd2bb4d1e654846356309a2d97fee00000000;
 }
 
-lsr {
+lslc {
+  # --- Simple sanity checks ---
+
+  01 2 07;
+  01 4 1f;
+
+  7 -1 0;
+
+  # --- Copy shifts ---
+
+  01 0 01;
+  0123456789abcdef0123456789abcdef 0 0123456789abcdef0123456789abcdef;
+
+  # --- Single bit shifts ---
+
+  01 1 03;
+  ff000000 1 01fe000001;
+
+  # --- Word-size shifts (assumes 32-bit words) ---
+
+  0123456789abcdef0123456789abcdef 32
+  0123456789abcdef0123456789abcdefffffffff;
+
+  # --- Random tests ---
+
+  13bbec3a734e0b8b5155600b0826b913 90
+  4eefb0e9cd382e2d4555802c209ae44fffffffffffffffffffffff;
+
+  d6ca6a99fe49b256f80e9643e2bd4f3e 80
+  d6ca6a99fe49b256f80e9643e2bd4f3effffffffffffffffffff;
+
+  c94784b40d54de614084915915531ddc 59
+  064a3c25a06aa6f30a04248ac8aa98eee7ffffffffffffff;
+
+  a63c314a39cc37f950b3d530c95ead00 84
+  0a63c314a39cc37f950b3d530c95ead00fffffffffffffffffffff;
+
+  842d03a339f5004cfd311e2bb23216ac 62
+  210b40e8ce7d40133f4c478aec8c85ab3fffffffffffffff;
+
+  9a8e659739bf9ee7aa908b7c058c5e7e 123
+  04d4732cb9cdfcf73d54845be02c62f3f7ffffffffffffffffffffffffffffff;
+
+  287f5774f212db87bcd83a1bbb7b1ad5 6
+  0a1fd5dd3c84b6e1ef360e86eedec6b57f;
+
+  ec1739174d9d4438d3093cf378605a5c 63
+  760b9c8ba6cea21c69849e79bc302d2e7fffffffffffffff;
+
+  3dfa8ad6a60a783639d05aa5fbfd993d 46
+  0f7ea2b5a9829e0d8e7416a97eff664f7fffffffffff;
+
+  e4e93a80b6d25b34c23aca3a0d06d76c 63
+  72749d405b692d9a611d651d06836bb67fffffffffffffff;
+
+  5a4cf5becb4b64a1a31637c91b6415fd 102
+  16933d6fb2d2d92868c58df246d9057f7fffffffffffffffffffffffff;
+
+  d92f60928b67416c1e20bd9e09026115 69
+  1b25ec12516ce82d83c417b3c1204c22bfffffffffffffffff;
 
+  eae78f56200d7734f7eb68479fe09d51 18
+  03ab9e3d588035dcd3dfada11e7f827547ffff;
+
+  4c9c215ead951513d969d66614016f6e 28
+  04c9c215ead951513d969d66614016f6efffffff;
+
+  5cb1e4d625eac0393644fe6a7e3ff788 33
+  b963c9ac4bd580726c89fcd4fc7fef11ffffffff;
+
+  68b23795968766c77b1897c88a5d6ba8 78
+  1a2c8de565a1d9b1dec625f222975aea3fffffffffffffffffff;
+
+  3d96cd168c74f9015afb691d629f3f6d 72
+  3d96cd168c74f9015afb691d629f3f6dffffffffffffffffff;
+
+  38fa8f63dc426399e0f9b5c01231e02c 95
+  1c7d47b1ee2131ccf07cdae00918f0167fffffffffffffffffffffff;
+
+  90176b493061899ec95677ccc58b8cdf 78
+  2405dad24c186267b2559df33162e337ffffffffffffffffffff;
+
+  0706e95da68f32a4231ab184d16cbff7 33
+  0e0dd2bb4d1e654846356309a2d97fefffffffff;
+}
+
+lsr {
   # --- Simple sanity checks ---
 
   04 2 01;
   10 4 01;
+  7 -1 0;
+  7 32 0;
 
   # --- Copy shifts ---
 
@@ -205,15 +319,15 @@ uadd {
 
   00 00 00;
   00 01 01;
-  01 00 01;  
+  01 00 01;
 
   # --- Carry propagation tests ---
 
     ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
-                                                          01
+                                                         01
   0100000000000000000000000000000000000000000000000000000000;
 
-                                                          01
+                                                         01
     ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
   0100000000000000000000000000000000000000000000000000000000;
 
@@ -410,7 +524,7 @@ umul {
   45 01 45;
 
   # --- Random tests ---
-  
+
   4162c300b3e157e9cd1301d499c20121
   10549901fc6dcb85882440087bd398ff
   042bc7ac8fe08ceefb098f286cdd84fd037906ead144324e361c488a221db7df;
@@ -490,6 +604,55 @@ umul {
   08d95fc1d6dd6b9423c7bb033598df0c
   6c03f5958677efd383509141bf257375
   03bbd76f19ba19e3f255c24063f6384d4ac913d9e582392589a525195bcc547c;
+
+  # --- Karatsuba regression ---
+  #
+  # This bug was caused by kmul (a) choosing the split point too low on
+  # odd-sized inputs and (b) not allocating enough workspace.
+
+  21a9269d7b8b63cf18faa933b3c868ba1e8cb3f00b57e197709abf96eeb9bf12e8fe22b3
+  0144c992b68e3ca712678215d5bc968702ccfea17717737ba501a38d26fa5091ba
+  2ab495f91afd7c36f85ece6fd58577f995de88d62a98a07c6d9e3500ae67b0f100bc709d1f30894662774d0cadfba091788c427cc6f4bacb26e42cf92f6e4494e03c990e;
+
+  # --- Larger number tests for Karatsuba ---
+
+  416e63549e2cf08fb225058b3545cb4a47cbf9
+  de38c473c27f7bdef02a084192b3e17f435cf7
+  38cc3c7f360737411df7b52a222a3672c6e0d39f0a868479176a6143e1129d44d5aa61be493f;
+
+  aa20b1355073f21c57530d2f90bc40e47ac463
+  8315dfa60e97ff3dab7a6f61fcec2cd5b6f127
+  571d43fda6ce14a78534ac72c50b58738d62630766a59a7cec1a63433e499b1b5eac5ef71e15;
+
+  f641594177c8c364d922c659a8f7ae0460c7d74b266c8cc258ad5f
+  5948dd29fc5172c37c31da6957779a1bebe452d8deba26c5d3d390
+  55e2cf27aa49f938584dca4044d944077e226206c6f8c7688e8760f3b5c106413fd0ef4b63a97991da86fd113ff4822a41f76913d270;
+
+  a4170f55dfa135c4bdd3a921a8c1567eebc6b799fb62b0dd27b089
+  7b7d619e07a5d01427348c05605f67196b2923b074787c375977ac
+  4f277232c75290f0c5fed384dba2aaa23fe4a360ea63ee45fb6c0134b36a09a9163f3c767d498b8dcd31e5deaef386d4a9b7d85b4b0c;
+
+  250e7a0c7035df81429572d3f772720e723b710d54b9eb5f16814117980f0559bf12b82e00c5b3904e
+  1be3c88b01ce53a70c12f74dcc247823846ac6c06a9cb41b86794900006045f05e29da23b81523aa9f
+  04097fbcf75616fef7b6b91680963f7e0cf1bf72bc5f453e46136fc92b20ae8a30d7ae7965f8271de854442b93562ebaa9ee09fba4a7b79ef8b26718b12424419dc301496dc0d6cfb04e4f7a3a3729046c72;
+
+  af3148a72dcf1340f6b5a3b2fc1cacd7e6f9e60a13de5c91c37bb850f0e930683c2dc96882a9f62b76
+  48603cc656908b34c70ed826da8c3414d5845100f53cb6f9f370a4c7708a9b8ffd787537048f89493a
+  3187b8818bf644805c880d189bbf606ca23e01431cf5b3b633db48a1202aa346f6a0e3958c7264fa1de2d92660345e820f4f3659cf0040a28fb9b725f7ab83610c9c056062326f776ce871696eede0507ebc;
+
+  0b1cc934a2f6244b93c8ac10881de20349d133642ac19fa0be3acacbf4429d0ec7bbad2f41534a693647b7c02e683cde249e36f008fb68e96de65c8a268eb1ea
+  12444899c13f0ee85a4f47024f06d8a5746f0d9fec02e57c6d87a7bba17c1454fe6387bff5b96e38ce6142b9eebe249865c52b617b8966e6f93b16f612a91155
+  cafcf1ea9f16a56f9ac4635d58992a789c51b6d7e53b5e1d8b59d5c1850c5c6ac2297839af44b29d5cf440772f98fd9d090ccec2d56adeb113bd3459d620b0b02679b72f3170ea8e2bd4486eebf2496d8be01cfe86923e5bbeb6f91582dfb95c6ef0a52cbc068081dc363b31dbd2ed80e3267d973ea39f82e276002eab9cb2;
+
+  3ba5a9c550b8cf6c3b87cc106b6551221a0dc90ac193ebcc526e4e5f53cf012fa6e05b155dcb3c4c0e1a90a01062a67ec434f6744195349194770711ea836a8b
+  54f04f121d22db842523e9bf75727d5b0e9ef17e6d727918894927fade87ceeb2106684c4af7c49653425e29f7a91abf8adec4de2ca499df2534644397e454ac
+  13ca59703f4c087c16a9a7bc7022904a37a469c1d0fd9fa7ffabe8f7d887fe1572c0bf5c75fde6913b565f8106bba9c26c9bbce190a9b8967112d74c0ac3d4ff9d2a385b96833e3c456d5601c74d8d2c9fff35abc60e7cc15d7c680f20757c13a415f1b8fbe3c6c32434aa36c528473dd20ea39f0e5ee22d1cd23040900d3164;
+
+  # --- More Karatsuba bugs ---
+
+  3fef06998b0ddd140e01527426ea409b2b9e640f223dfd652229fd17eb99d44f6be6d4935505df676f48c8fcbfe2d5096345d6509267aa40c54d427f0cce45cd0f8fa7e4a22492d7ed4ffa45e3c0e5e3c25c841943fb2cecd6ee9275ae93c4e15e2d9f8f317c44c541ed52a6338b0fb9f7f7f4dea78cf7ef5201837c00a6d4d2
+  0260acc6378341b2b894dacab3a44b914f19292bb32898b155584a406161bb04ad9c14db20888dfcdab613b368b5c699305c4e9b226d90f9523fbcb6293407bd2bb18bf7bdba8539fb577f19b72124c2d83a2bc31f44366e917ddc705085b79fe9e0df0e98e4f6ae3df63d9b321382c18b95de1dc4d1db93b3092c9c6f8c9764
+  9802d5c5d5a73f9d4e694a8920f951ce4bfe80c13a35cd5332a556136b83495a2e9b4d2ed53aae1218d2e1c41349311f86b1ee1f2ad5cd3c5b264e8e68906ca45bd7d0fc8e8a5a9648f458cecba41fd0848a04f506bb11ddb378f3214085cf865ba5533cfd73b28b1e12784f447b156f59a3b68e6ec68303ddfce59ce33ca386ff3316e6a5e6f9b4201682aa9e59a6d7cb9315a492457640acca19fc7dc3a25a316fea9a0f1d32838b7f911650647f996551263c2d001fa1c720753afca316c7137300ff93f2ddd2846ce14c55d0ead626f681bd11707f9674905396a9bc9a889eae721ab6407586880a95575a968b43bdf50323627aa0fcddfa4e198b0008;
 }
 
 usqr {
@@ -562,6 +725,44 @@ usqr {
 
   c4245e0ce04fe1151ca17eb8aeb6e3e3
   9647b52e4da6dc80171bd5495ab519835e871bf915ee7e59f1fe2ac165a05b49;
+
+  # --- Large tests for Karatsuba ---
+
+  8390d2dfc9770526e8c4820e1cccca0e8e19d2
+  439d89bef1a65f537e59e74590df3ef10b7e78066ac2af7b5c910e1929de102b491b9f92b044;
+
+  26c4cb564d57970bc3dd00c0c1690c7f1a2e9a
+  05df03a59c9e6ab7bfed79ff8f32811303e46f94c2e8d9abcab5bdac1040e7fdaf5a4bc3b4a4;
+
+  599b3cceca39690c06425127a95b84310cddef
+  1f5d4e6a797662648e4b09abeee439415b76cae52e7cf9db1a54b7f99afb9c00b6130cce8521;
+
+  485b65b3d5edb34810402943ccfbe37a137f8f
+  147389d69e9730f86b04a1782fd15611e6f8dc2e99abc812be0cb82efb2a1ad538aa7ac931e1;
+
+  5a243e54da1f87a8fe23c8b0988b3574aa77c1fe620a5d25b8e03295aebe6c6e135a17
+  1fbd80f54068ba081e793c1aad443094416a75e2e708337618e4ff02ca9dd26bad87cdc0f758342df39a56625c956c971b1f7f18f7d3cb6a1880a574bb7b06a6ca4a431e2e11;
+
+  f5c57a7610feec56586de369136ee25aaf5d3861ad80033410c410658332ca856e4cce
+  ebf394bbb0d2d75ba78b75ae018c77f417cc1c67f0aa587d070980386e14f2b59d9a580d8d483b4df7f6a8d4a44ec8786a87d1da031bb5c288c3afc65d931471786c2412f5c4;
+
+  5bc4457e00bcacf257200a96eadf90359cbd9f6a2c2c69b5ea2e4c5d3939f0ce100c06
+  20e51fe210546e478bfb9d2b0418df921974417799951533f317498439caed52a75c4c66db81910b3fc4f4fb3711cc25f2b4ef151a2023b6e52e64e1d5b7dffb0b9b29509024;
+
+  4b51f1e0a9206173d39a0f1f4eea558dbd9d1ca2d41671b2d27b1b77391e76504e14c0
+  16291df497ccc32ee92a9037b78ff10828c2645dfbf91541f3a0d963892d59c5cd966ffe1e1ebb2dfe6f434fae44da11ae2d2357876b711feba596612c102b8905c8a6ae9000;
+
+  10f63541b2bc5a7d241f887d0b3d182dc473a06c4fb275259112b2fecc9455d7b1eb5b2e9b5c3646c35121d05f1ae99f1ad990c7f0e48b002bd5fdd253c68b56
+  011fb3729baf522bcaed9a966645754804b2cc80168de9f93544e17d5b6d6b81c516f68b72580257f15e3f95bc6eec22608c3055de04051598bf4a76975d111a59d6b02a2fc42de65926cee5d5b97b6c7fc85e00dd59bfdac2c95bc80b7657582b2853244e55b507594a83d5bd87b7a83016dbbc104ce596bdaaed6d98de80e4;
+
+  9e40b3c041505a5e266109f752d85ae3abcbdd28bfc70bbb2c7228bc1564ea893cdda0350689610b74babfe45b14da9708f28c22e3999c841fc70075dd0535cb
+  61d3ee3baef64371ce0416d3f5a6e687903413ad06e85ebbffb9ea0ae9e8cc290fe9dc1cec429e0a294b18121ee29755baf4306861e092e5c1f1def03953f559766787a222368b64594b7be2eeea0698d1fc630446714e681210b5a66e0433b6c43038c0ff213cd14fc0a1fb71789d57b097ab44d859f8bc912f2a89a33baef9;
+
+  d35af50f523d29f53bf0126ccddf4f3052ddb44eeaead360b5f36aad902ba105a921880cefb12caf5e1b3719a40596732d265e996e491f82ca2edf08adca131e
+  ae7f10487aecfa7f91217020f96a1cb00d81545deaf9730daa2c7113e84e76c7e54a1b14971d26750816a696d55622ae1dbd56befdc12a656e66e1d10e87c3bc209e0903635784af6d48a4d7ec84634efb91b7efbfff724bb50ace7d4684d2e72eb7eef84ed5cfd14a7602ceded675da541646febcaa285396b23338b8c57784;
+
+  3df659f884c6a31c5b332efc44fbd70fea46b81adb241fc651af038380f8c476a471f06382ebe55eba339d84edb33a03002ac505d93c61a42ba20e36a691c287
+  0eff53f178849510a118db72c5620423c2991365b06e8caa76300f3df554cf8830c9833f6ec1d33c850b1bb380e33a486a9963b63b5228229fd7e9bdd308bc810aa5e74ccc0e65a2af40c9a287c67e69e841495b0221110f35ed6319bda0dcb0b02174b666df4766eea05481f6a80fe4b93a06fe475d58ae3002303904bee331;
 }
 
 udiv {
@@ -673,4 +874,17 @@ udiv {
   620d87bb63872a40fc2092b0ed7d3ec4b648be41
   0155177e99a8a5113226ff8270
   2ea2205327e66d75990cc999fc2380883ee4591a;
+
+  # --- Bugs ---
+
+  1a923b3406cbe81b093ce418f6a73107f504502b2e3d1b200762fcf6062723de405cab0aea00000000000000000000000000000000
+  184f03e93ff9f4daa797ed6e38ed64bf6a1f010000000000000000
+  0117d3db34ad005954459be9abedd0e5deb4ea0000000000000000
+  00;
+
+  ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a63a3620ffffffffffffffff
+  7fffffffffffffffe487ed5110b4611a62633145c06e0e68948127044533e63a0105df531d89cd9128a5043cc71a026ef7ca8cd9e69d218d98158536f92f8a1ba7f09ab6b6a8e122f242dabb312f3f637a262174d31d1b107fffffffffffffff
+  02 01;
+
+  26737e 0ffffc 02 067386;
 }