summaryrefslogtreecommitdiff
path: root/bignum.c
diff options
context:
space:
mode:
authorYukihiro Matsumoto <matz@ruby-lang.org>1994-07-18 10:19:15 +0900
committerTakashi Kokubun <takashikkbn@gmail.com>2019-08-17 22:09:29 +0900
commit200e0ee2fd3c1c006c528874a88f684447215524 (patch)
treedf2252585f3000878a15123d98ccb08124306b90 /bignum.c
version 0.49v0_49
https://cache.ruby-lang.org/pub/ruby/1.0/ruby-0.49.tar.gz Mon Jul 18 10:19:15 1994 Yukihiro Matsumoto (matz@ix-02) * parse.y: 多重代入を処理するルールにバグがあって, 3要素以上の多重 代入に失敗していた. * eval.c(rb_eval): 多重代入で, 右辺が配列でない時には`to_a'メソッ ドで配列に変換して代入するようにした. 今までの仕様だと右辺値が第 1要素にそのまま代入されていたが, structなど配列に変換できるもの は変換した方が嬉しい気がする. * dbm.c,dict.c(delete_if): メソッド追加. * process.c(wait,waitpid): システムコールwaitpidまたはwait4がある 時はそちらを使うように. configureもそれらをチェックするように変更. * dbm.c, dict.c(clear): メソッド追加. Fri Jul 15 10:54:45 1994 Yukihiro Matsumoto (matz@ix-02) * array.c(Fary_fill,Fary_clear): メソッドを追加. * string.c(Fstr_split): $;の値が長さ1の文字列である時, これを正規 表現化しないで, 単なる文字として分割する. * string.c(Fstr_aset/Fstr_aref): インデックスが文字列の範囲外だっ た時の動作をArrayを参考に修正した. * array.c(astore,Fary_aset): 領域をreallocした後, ゼロでクリアする ように. 今まで配列にゴミが入っていた. * array.c: []/[]=でのインデックス関係を整理. 基本的に負のインデッ クスに代入しない限り例外は起きないように変更した. 必要に応じて適 当に解釈して, 必要ならば領域を拡張するように. Thu Jul 14 11:18:07 1994 Yukihiro Matsumoto (matz@ix-02) * autoexec.c: 削除. autoload関係の機能は今後検討しよう. * dict.c: 辞書クラスの正式名称をDictに変更した. 別名としてHashを用 意した. 今までDictionaryなどと長い名前にしていたが誰も使っていな かったしね. *BACKWARD INCOMPATIBILITY* * parse.y: Dictを生成する構文を追加. こちらを{..}にした. * parse.y: 配列を生成する構文を[..]に変更した. 過去のRubyスクリプ トとの互換性が保てないが, Dictを生成する構文を導入するに当たり, perl5に合わせて(意識して), 変更する時期は今しかないと考えた. *BACKWARD INCOMPATIBILITY* * eval.c(Feval): eval()でメソッドを定義する時, 定義されるクラスを メソッドの所属するクラスにした. 今まではObjectクラスに定義されて いた. * parse.y: ローカル引数がない時のeval()で落ちていた. Thu Jul 14 11:18:07 1994 Yukihiro Matsumoto (matz@ix-02) * eval.c: メソッドが存在しない時にはKernel:_undefined(id)が呼ばれ るように. しかし, rubyでは個々のメソッド毎の処理よりも, クラス 単位の処理が必要な気もするなあ. * autoexec.c: 削除. autoload関係の機能は今後検討しよう. * dict.c: 辞書クラスの正式名称をDictに変更した. 別名としてHashを用 意した. 今までDictionaryなどと長い名前にしていたが誰も使っていな かったしね. *BACKWARD INCOMPATIBILITY* * parse.y: Dictを生成する構文を追加. こちらを{..}にした. * parse.y: 配列を生成する構文を[..]に変更した. 過去のRubyスクリプ トとの互換性が保てないが, Dictを生成する構文を導入するに当たり, perl5に合わせて(意識して), 変更する時期は今しかないと考えた. *BACKWARD INCOMPATIBILITY* * eval.c(Feval): eval()でメソッドを定義する時, 定義されるクラスを メソッドの所属するクラスにした. 今まではObjectクラスに定義されて いた. * parse.y: ローカル引数がない時のeval()で落ちていた. Tue Jul 12 09:41:28 1994 Yukihiro Matsumoto (matz@ix-02) * pack.c: uuencode形式のサポート. * `-0'を`-R'に. 出力レコードセパレータをコマンドラインから指定する 方法はなくなった. どうも, 仕様がゆれるなあ. Mon Jul 11 09:51:24 1994 Yukihiro Matsumoto (matz@ix-02) * ruby.c: `-r'オプションは`-0'オプションになった. 当面は`-r'も有効 だが変更される可能性がある. `-R'は当面はそのまま. * version.c: version表示に日付を含めた. * parse.y: private methodの復活. RubyのprivateメソッドはC++におけ るprotected methodに該当するもので, `@'で始まる名前を持つ. * env.h: struct ENVIRONの定義を分離. * parse.y: `\$var', `\@var', `%var'も許すように. * variable.c(Fdefined): idも引数として受け付けるように. * parse.y: if文/unless文にキーワードthenを追加. thenなしというのは, 意外と間違いが多いので. もちろん省略できる. Sat Jul 9 02:16:04 1994 Yukihiro Matsumoto (matz@dyna) * eval.c(rb_eval): class/moduleの評価で新しいスコープを割り当てて いなかった. スコープ割り当て部分をrb_call()からrb_eval()に移した. * eval.c(rb_call): realloc()に渡される事のある, ローカル変数用の領 域をalloca()していた. たまに落ちるわけだ. * string.c(Fstr_times): 割り当てた領域を越えた部分を変更していた. Wed Jul 6 15:52:42 1994 Yukihiro Matsumoto (matz@ix-02) * socket.c: Socket -> BasicSocket, RawSocket -> Socket に改名. * string.c(ucfirst,lcfirst): 最初の1文字だけの大文字/小文字変換. * numeric.c(chr): 整数の文字列化メソッド. * inits.c, dbm.c: DBMが使えない時はクラスそのものを定義しないよう にした. 利用できないクラスはnilとすることを今後のポリシーとしよ う(いままではアクセスした時点でエラーが発生していた). autoexec() のあり方も検討が必要になりそうだ. * bignum.c(bigadd): バグ修正. Thu Jul 7 11:12:18 1994 Yukihiro Matsumoto (matz@ix-02) * eval.c(Fload,Feval): eval_treeをクリアし忘れていた. * _inspect: オブジェクトを可読形式の文字列に変換する(主にデバッグ 出力用). Wed Jul 6 00:57:18 1994 Yukihiro Matsumoto (matz@dyna) * numeric.c, bignum.c: 整数に対する`[]'演算子. nビット目がセットさ れているかどうかを返す. Tue Jul 5 12:48:39 1994 Yukihiro Matsumoto (matz@ix-02) * io.c(Feof): 追加. コマンドラインからなる仮想ファイルについても EOFが検出できるように. * ruby.c: -l/-r/-R/-Xオプションの追加. * ruby.c: -n/-pオプションのloopの付加などをメインルーチンに移動し た. これで, オプションの解析途中で(`-c'オプションのせいで)終了な どといったことはない. * io.c(Fgets): 高速化. 凝ったことをしない方が速かった. 虚しい. Mon Jul 4 15:55:48 1994 Yukihiro Matsumoto (matz@ix-02) * Socket:getsockname/getpeername - ようやく仕様が安定した. * io.c(Fgets): eachでgetsを記述するのではなく, getsでeachを記述す るようにした. Fri Jul 1 10:35:49 1994 Yukihiro Matsumoto (matz@ix-02) * $ENV[env] = nil/$ENV.delete(env)で環境変数を削除できるようになっ た. $ENV.deleteは環境変数の以前の値を返す. * !~の定義が間違っていた. * Dict,DBM:[]= - nilの代入によって要素を削除できるようになった. こ れにともないnilはDictの要素になれなくなった. * ソースの整理. 盲腸のような使われていないコードをなくしたり, 変数 名を付け変えたりした. Fri Jul 1 00:21:29 1994 Yukihiro Matsumoto (matz@dyna) * Array:join() - 要素数0の配列に対して空文字列を返す. * RawSocket:open(),socketpair() - 文字列で指定できるドメインとタイ プをいくつか追加した. Thu Jun 30 13:51:29 1994 Yukihiro Matsumoto (matz@ix-02) * -fオプションをなくした. 昔(loadのなかった頃)の名残なので, 今となっ ては必要ないだろう. * -sオプションを追加. perlの-sオプションと同じ動きをする. * RawSocketクラスを提供する. Socketに対するシステムコールレベルの アクセスが可能になった. Thu Jun 30 00:27:19 1994 Yukihiro Matsumoto (matz@dyna) * Socket - bug fixes. * linuxではsyscall(SYS_select)が正常に動作しない. * Socket:addr,peeraddr - 配列としてsockaddrの情報を返す. Wed Jun 29 00:14:20 1994 Yukihiro Matsumoto (matz@dyna) * Socket:setopt,getopt - setsockopt(2), getsockopt(2)へのアクセス を実現. * sprintf() - rubyにはunsignedは無いので, %uを取り除いた. * sprintf() - %b, %x, %oでは2の補数表現, %B, %X, %Oでは符号付き表 現で出力するように. ここ数日でsprintf()の仕様がゆらいでいたが, これで落ち着きそうだ. Tue Jun 28 14:42:03 1994 Yukihiro Matsumoto (matz@ix-02) * Bignum:<<,>> - 2の補数をとる処理を除いた. シフト演算には関係ない 処理だった. * Bignum:^ - bug fix. 符合が反対だった. * sprintf() - 2進出力子"%b"を追加. * sprintf() - %x, %oでFixnumを出力する時, 2の補数表示を行なわない. * sprintf() - %x, %oはやはり負の数の時は`-'を出力するように. Mon Jun 27 14:56:13 1994 Yukihiro Matsumoto (matz@ix-02) * sprintf() - Bignumについても%d, %oは(2の補数表現に変換して)正の 整数を表示するようにした. * Bignumに対する論理演算の定義を修正した. 負の数は2の補数表現であ るとみなし, かつ仮想的に左側に無限に1が連続しているような演算結 果を得る. * Fixnum:<<,>> - 符合付シフトに変更. * Bignum:>> - 負の整数のシフトに対応した. * __END__, ^D, ^Zでスクリプトを終了できる. * -xオプションを追加. #! ..rubyなる行まで読み飛ばす. * -cオプションを追加. コンパイルのみを行う. Sat Jun 25 01:37:21 1994 Yukihiro Matsumoto (matz@dyna) * Fixnum:<< - 必要に応じてBignumに拡張して左シフトするように. よっ て, シフト幅が32を越えるとCやPerlとは違った値を返す. Fri Jun 24 10:01:28 1994 Yukihiro Matsumoto (matz@ix-02) * ioctl()/fcntl() - システムコールを呼び出す前にバッファの大きさを 調節するようにした. * String:toupper/tolower - 文字列を置き換えたコピーを作るのではな く, 元の文字列の内容を変更するようにした. * inplace editを実現した. perlと同じように`-i'オプションで指定する. もっとも, こちらはMS-DOSのこととか考えてないけど. * デフォルトの出力先を追加した. 今までは$stdoutに代入するしか方法 はなかった. Fri Jun 17 10:55:08 1994 Yukihiro Matsumoto (matz@ix-02) * 環境変数にアクセスする方法としてgetenv()/setenv()以外に$ENVを用 意した. $ENVは文字列-文字列の辞書であるかのように動作するEnvDict オブジェクトが代入されている(eachはassocを与える). * nilに代入するとcore dumpした. コンパイル時のチェックを強化. * Struct: struct_new()の引数をGCプロテクトする必要がある. せめてス タック領域だけでもスキャンできるようにしなければいけないんだろう か? でも, 移植性がなあ. Fri Jun 17 01:01:46 1994 Yukihiro Matsumoto (matz@dyna) * Time::asctime() - 日付のフォーマットで日が落ちていた. * Stat: StatはEtcなどと同様にStructで実現したので, Statクラスは無 くなった. Thu Jun 16 10:32:23 1994 Yukihiro Matsumoto (matz@ix-02) * bignum.c: いくつかのバグを修正した. Fixnumを渡すべきところで普通 のintを渡していた. 失敗. * big2str() - 1桁ずつbaseで割る代わりに, 4桁ずつ割算を行なうように した. これで多倍長割算の回数が1/4になる. さらに整数->数(文字)へ の変換をテーブルを用いるようにした. * rb_ivar_get_1() - すでに何らかのインスタンス変数を持つオブジェク トでは, 未定義のインスタンス変数の値が不定値になっていた. * yylex() - インスタンス変数の認識に失敗していた. attr()は正しく動 作していたので, 混用すると動作しなかった. 全部違っていたから動い ていたのね. * Object:attr() - すでにアクセスメソッドが定義されている時にはデフォ ルトのアクセスメソッドを定義しないようにした. もっともアクセスメ ソッドと同名のメソッドの区別はRubyには存在しないけど, それは仕方 がないよね. * pack.c: エンディアンをautoconfで判定するようにしたので, v/Vが使 えるようになった. またntoh?()/hton?()も自前で用意した. * Stat: st_rdevをアクセスするメソッドを追加. さらにシステムがstat 構造体にst_blksize, st_blockを持っているかをautoconfでチェックす るようにした. * ドキュメントを少し整備した. * INT2FIX()のうち, 31bit幅が保証できないものは, int2inum()に置き換 えた. Wed Jun 15 10:18:27 1994 Yukihiro Matsumoto (matz@ix-02) * sprintf() - bignumの出力の時, 出力幅を正しく計算するようにした. * str2inum() - baseが0の時, baseを自動判定するように(0xで始まる時 16 進, 0で始まる時8進). Tue Jun 14 16:08:42 1994 Yukihiro Matsumoto (matz@ix-02) * gc.c: Bignumを追加するのを忘れていた. 組み込み型を追加した時には 必ずmark()とsweep()にその型に関する処理を追加する必要がある. * bignum: 割算も動いたような気がする. アルゴリズムを理解していない ので, 自信がない. Mon Jun 13 14:36:55 1994 Yukihiro Matsumoto (matz@ix-02) * まだサポートしていないメソッドなどがあるが, 曲がりなりにもBignum が使えるようになる. これでioctlも使える. Fri Jun 10 17:26:42 1994 Yukihiro Matsumoto (matz@ix-02) * Comparable: 基礎となるメソッドを`=='と`>'から`<=>'に変更した. 今 後Comparableのサブクラスは`<=>'だけを定義する必要がある. Wed Jun 8 13:12:18 1994 Yukihiro Matsumoto (matz@ix-02) * Need_Fixnum()をほとんどなくして, NUM2INT()で直接intに変換するこ とにした. これで31bitに丸めて桁落ちをおこす問題がなくなる. Tue Jun 7 09:45:31 1994 Yukihiro Matsumoto (matz@ix-02) * ruby.h: マクロFIXABLE(n)を追加. ついでにFIXNUM周りの定義を変更し て, 移植性を高めた(つもり). * C++の予約語であるnewを削除した. しかし, もうひとつの予約語である classに関しては, 置き換える単語が思いつかないこともあってそのま まになっている. * 31bitを越えそうなINT2FIX()を関数呼び出しに変えた. 将来bignumが導 入された時には自動的にbignumを返すようにする. * readline() - 引数の`-'は標準入力を意味するようになった. * ruby.h: 右シフトが論理シフトか算術シフトかは処理系依存のようなの で, ruby.hでcppを使ってチェックするようにした. これでうまくいく と思うのだが, 手元に符合付intを論理シフトする処理系がないので確 認できない. NEWS-OSのCCは確か右シフトはいつも論理シフトだったよ うな気がするんだけど…. Mon Jun 6 10:10:22 1994 Yukihiro Matsumoto (matz@ix-02) * FIX2INT()の定義を変更した. どうして昔はうまく動かなかったんだろ うか? もしかして, 右シフトの符号拡張は処理系依存? * FIX2INT()とFIX2UINT()を使い分けるようにした. もっともfixnumは31 ビットしかないので, 本質的な解決にはならないのだが(ioctlが組み込 みたかった). * printを関数的メソッドから通常メソッドに変更. 引数が与えられない 時にはレシーバをプリントするようにした. これでprintをメッセージ 形式でも実行できるようになった. 例: ruby -e 'readlines().sort.print' 上のスクリプトは, 引数として与えられた(あるいは標準入力から読み 込まれた)文字列を各行毎にソートして表示する. * eval.c: argc,argvパターンで引数を受けるメソッドに引数が一つも与 えられない時, argvがnilになっていた(argv[0]にアクセスすると落ち てしまう). * _exit()を追加. こちらは例外処理など行なわない. * dbmクラス: クラス名称をDBM(大文字)に統一した. Sat Jun 4 00:51:04 1994 Yukihiro Matsumoto (matz@dyna) * ループ変数にも属性や配列要素を指定できるようにした. Fri Jun 3 09:49:48 1994 Yukihiro Matsumoto (matz@ix-02) * 多重代入において, 属性代入, 配列要素への代入も行なえるようにした. * Need_Fixnum(): nilを0に変換するように. * Enumerable:min, max, index, includes - 追加. min, maxは要素が `<=>'メソッドを持つことを仮定している. * Dict/Dbm:length - 要素数を返すメソッド. * Dbmクラスにto_aメソッドを追加. * Sunにおけるsortの誤動作の件, 昨日の修正でfixされた. しかし, それ でなぜ動かなかったのかは明らかではないが…. 比較関数がどんな値を 返しても指定した領域外をアクセスするのはバグではないか. * ファイルの全内容を読んで, 各行を配列として返すメソッドはpythonを 参考にして`readlines'という名前にした. それにともないgetsに対し てreadlineという別名を用意した. Fri Jun 3 00:08:38 1994 Yukihiro Matsumoto (matz@dyna) * Array:sort - 判別関数の戻り値はFixnumではなく, Intであるべきだっ た. 間違い. Sunで動作がおかしかったのはこのせいかも知れない. Thu Jun 2 11:48:37 1994 Yukihiro Matsumoto (matz@ix-02) * IO:read_all() - ストリームの最後まで入力して, 各行を要素とする配 列を返すメソッドを追加. また関数メソッド read_all()も追加した. これは引数のファイルから読み込んで各行を要素とする配列を返す. 意 味的には def read_all() ary = {} while gets() ary.push($_) end end とほぼ等価である. * String:atoiメソッドを削除. to_aメソッドからaが配列であるとの連想 を呼んで, 混乱を招かないため. 代わりにto_iメソッドを使うこと. * 配列への変換メソッドto_aを導入した. 通常のオブジェクトは自分自身 を唯一の要素とする長さ1の配列を返す. 配列は自分自身を, 辞書はキー と値のペアの配列を返す. Enumeratedをincludeしたクラスは, eachが 返す各要素を含む配列を返す. * file.c: 不定個の引数を受けとるメソッド(chmod,chown,utimes)を書き 換えて, 整理した. それに伴い, 最初に全ての引数の型チェックを行な うようにした. 型チェックに失敗すると処理を行なわずに例外を発生さ せる. * configure.in: 不必要なテストを行なわないように修正した. Tue May 31 10:41:08 1994 Yukihiro Matsumoto (matz@ix-02) * String:pack(): 2進数の文字列変換(B,b)で0と1が逆だった. * Math.c: 実数系のメソッドに引数として整数が渡された時に自動的に変 換するようにした. * toupper(), tolower(): 文字列の判定ミスで変換されていなかった. * getopt_long()の仕様によって, スクリプトへの引数がインタプリタの 引数だと解釈されていた. 引数パターン文字列の先頭に`+'を追加. * config.hを削除した. DEFINEはMakefileで与えられる. * sprintf(): "%d"に文字列が与えられた時にはアドレスではなく内容を 整数に変換するようにした. ついでに浮動小数点数も変換するように変 更した. * regexp.c: rubyの拡張正規表現(\d, \D, \s, \S)の処理で割り当てた領 域を越えてバッファに書き込んでいた. 処理前にバッファをきちんと拡 張するようにした. これで昨日問題にしていたメモリの問題は解決でき たと思う. * yylex(): ダブルクォート文字列中でダブルクォートを表現するため のバックスラッシュ表現ができなかった. Mon May 30 10:07:42 1994 Yukihiro Matsumoto (matz@ix-02) * 演算子`!'の右辺も条件式であるとした. これによって, この演算子を 再定義する人は混乱するかも知れないが, 大多数のこの演算子を使う人 は混乱を避けることができると思う. * autoconfを使って, 自動的にMakefile, config.hを生成するようにした. これで, 大抵のマシンでは`configure'を実行した後, `make'一発でコ ンパイルできると思う. * clone: サブクラスに対して用いられた場合, 元のオブジェクトと同じ クラスのインスタンスを返すように(以前はビルトインクラスの場合を 考えてなかった). * ビルトインクラスのサブクラスも作れるように, リテラルのあるクラス にもnewメソッドを追加した. * malloc()で落ちる. purifyが必要かも知れない. * re.c: rb_global_variable()の呼びだし形式の間違い. 変数へのポイン タを渡さなければいけない. * parse.y: ローカル変数の扱いに引数の評価順に依存する移植性のない 部分があった. * attr(): 属性設定のバグを直した. いつ内部仕様が変わったんだろう…? Sat May 28 23:08:18 1994 Yukihiro Matsumoto (matz@dyna) * 正規表現キャッシュの文字列一致判定をポインタ一致から内容一致に変 更した. そういえば文字列リテラルは一回毎に新しくオブジェクトが生 成されるのだった. Fri May 27 11:42:00 1994 Yukihiro Matsumoto (matz@ix-02) * 正規表現の文字コードのデフォルトを漢字非対応にした. これによって 若干の高速化が図れる. * trから文字削除(delete), 文字圧縮(squeeze)を分離した. それにとも ないtrのオプション引数はなくなった. Thu May 26 10:32:55 1994 Yukihiro Matsumoto (matz@ix-02) * スクリプト読み込みルーチンを書き直して, 通常ファイル以外のファイ ル名や空文字列がスクリプトとして与えられた場合に対応した. また, 標準入力からスクリプトを読み込む時に, 一時ファイルが/tmpに残らな いようにした. * Fixnum:id2name - IDから文字列に戻す関数. String:internの逆. * Array: 配列の範囲外の要素をアクセスした時に例外を発生させずに, nilを返すようにした. 配列は自動的に拡張される. * string:stripを追加. * -nオプションが-eオプションを複数指定した時も動作するように. * parse.yで<sys/types.h>もインクルードするようにした. * fname周りの細かいbugを修正. Wed May 26 11:45:10 1994 Yukihiro Matsumoto (matz@dyna) * 定数をキャッシュするようにした. 繰り返しが多い場合には有効のはず だが, 一度しかアクセスしない場合は遅くなるなあ. Wed May 25 00:42:24 1994 Yukihiro Matsumoto (matz@dyna) * 多重代入文(foo, bar = 1, 2)の採用. * 条件式部に文字列あるいは正規表現リテラルをおくと`=~'演算子によっ て`$_'と比較される. 更に`...'の両辺では整数リテラルが`$.'と比較 される. Mon May 23 23:27:03 1994 Yukihiro Matsumoto (matz@dyna) * &式 形式はなくなった. 代わりにkernel:apply(id, args..)を導入. * def op () ..形式の導入. opは再定義可能な演算子. * constantの代入時チェック. 既に初期化されている定数に代入した場合 は例外が発生する. * 多重代入文. Thu May 19 22:57:07 1994 Yukihiro Matsumoto (matz@dyna) * 複合文でもvoid valueのチェックを行うようにした. * untilの動作の修正(do..until型だった). Wed May 18 01:06:25 1994 Yukihiro Matsumoto (matz@dyna) * 移植に関する若干の問題を修正. * 別名の構文を「def a b」にした. * until/unless: 演算子から制御文へ. 例外を捕捉する機能はそのまま. * 選択可能な機能をconfig.hからdefines.hに移動. Fri May 13 23:20:21 1994 Yukihiro Matsumoto (matz@dyna) * -yオプションを新設. -dオプションからコンパイラのデバッグ部分を分 離した. Tue Apr 25 20:17:33 1994 Yukihiro Matsumoto (matz@dyna) * マルチバイト文字列を識別子に使えるように. 個人的には使いたくは無 いけどなあ. * `-v'フラグの状態を$verboseでアクセスできるように. * CVSの導入に伴い, バージョン管理の方法を変更. * 真面目にChangeLogをつける事にした. Tue Mar 8 10:09:25 1994 Yukihiro Matsumoto (matz at nws119) * %変数名 によるクラス定数を導入. * undef メソッド によるメソッド定義の取り消しを導入. * rb_get_method_bodyではthe_envを変更せず, rb_call()で明示的に変更 するように. これでresponds_toなどで環境が破壊されない. Mon Mar 7 17:46:15 1994 Yukihiro Matsumoto (matz at nws119) * 「&文字列」形式. 「式.文字列」型のメッセージセンドはなくなった. * 自己代入形式(+=. -=, ...) * obj.attr = expr形式の採用. Thu Feb 24 16:23:28 1994 Yukihiro Matsumoto (matz at nws119) * toint, tofloat, print_stringをそれぞれto_i, to_f, to_sに変更. * String:clone - Copy on Writeの実現. Tue Feb 22 11:11:44 1994 Yukihiro Matsumoto (matz at nws119) * re.c: マッチした文字列の保存に失敗していた. * trap: 可能ならば処理に時間のかかるシステムコール(read, wait, sigpause, select)をフックして割り込み処理の即答性を高める(DOSな どでは無理だなあ). * trap: 割り込みをその場で処理するか(迅速だが危険), 安全なタイミン グで処理するかを選択できるように. Tue Feb 17 11:11:12 1994 Yukihiro Matsumoto (matz at nws119) * trap: 割り込みハンドラ. Wed Feb 16 12:29:12 1994 Yukihiro Matsumoto (matz at nws119) * String:crypt: 暗号化ルーチン * "::"演算子の追加. a::b は {a, b}と同義. a::b::c は {a, {b, c}}と 同義(右結合). 同義とはいうものの, "::"演算子を使った方が少しだけ メモリ効率が良い. * Dir.rmdir(), File.unlink(), File.utime() -- 各システムコールへの インタフェース. * kill -- kill(2) I/F * select(): readのチェックではstdioにバッファリングされているかど うかをチェックするように. Tue Feb 15 15:08:31 1994 Yukihiro Matsumoto (matz at nws119) * file.c: statをキャッシュするように. * File:utime()を追加. * unliteralize(): フラグを破壊していた. * Bug(): coreを吐くように. * String:tr -- tr(1)互換. 引数パターンがちょっと違うけど…. Mon Feb 14 18:24:13 1994 Yukihiro Matsumoto (matz at nws119) * unless, untilが例外も偽と見なすように. * select() -- select(2) I/F * Array:pack, String:unpack: perlのpack/unpackの同等品 Tue Feb 8 17:11:10 1994 Yukihiro Matsumoto (matz at nws119) * setenv()のないシステムのためにputenv()を使ったコードも用意した. Mon Feb 7 09:52:44 1994 Yukihiro Matsumoto (matz at nws119) * 引数の一番最後に`*'を置けるようにした. これでrest引数のリストを 操作する必要が少なくなる. Fri Feb 4 18:23:26 1994 Yukihiro Matsumoto (matz at nws119) * ruby-mode.elを書き直す. ずいぶんましになったと思う. * 文字列リテラルのCopy on Writeを実現. これで文字列がリテラルであ るからといっていちいちcloneしなくても済む. Tue Feb 1 09:21:09 1994 Yukihiro Matsumoto (matz at nws119) * sub(), gsub()で, マッチした文字列を$&, $1..$9でアクセスできるよ うにした. 同時にマッチした部分文字列をコピーしておくように(元の 文字列が変更されても状態を保存するため). Mon Jan 31 15:16:58 1994 Yukihiro Matsumoto (matz at nws119) * プライベートメソッドの仕様を変更. 今までは同じクラスのメソッドか らしかアクセスできなかったが, サブクラスのメソッドからもアクセス できるようにした(C++におけるprotected メンバ関数). * メソッドサーチのアルゴリズムを改善し, 10%程度の高速化を行なった. * 高速化. Cで記述されたメソッドを呼び出す時にはsetjmpを呼ばないよ うにした. これでCメソッドを多用する場合には3倍程度高速になった. Fri Jan 28 15:44:04 1994 Yukihiro Matsumoto (matz at nws119) * sh-modeを元にruby-mode.elを作る. 演算子で終る, 2行に渡る文には対 応していないけど…. Thu Jan 27 11:35:19 1994 Yukihiro Matsumoto (matz at nws119) * freenode(): NODE_NILの解放忘れ. * 字句解析部のバグ修正(コメントの後の状態を戻し忘れ). * protect .. endのバグ修正. GC_LINKのネストが不正だった. * joinのバグ修正(使っているオブジェクトをfreeしていた). * splitのバグ修正(アルゴリズムがおかしかった). * fork()を追加. Wed Jan 26 17:09:56 1994 Yukihiro Matsumoto (matz at nws119) * ファイルテストメソッドの追加. * rb_autoexec(): クラスを初めてアクセスした時の挙動を制御できるよ うにした. これでautoloadも実現できる. これにともないメソッド unknownはなくなった. Tue Jan 25 15:51:36 1994 Yukihiro Matsumoto (matz at nws119) * Dbmクラス, Mathモジュールを作成. * -Iオプションでサーチパスに追加できるように. * サーチパスを変数$load_pathに設定できるように. * load(): ダイナミックロードを使えるようにした. Tue Jan 18 14:14:01 1994 Yukihiro Matsumoto (matz at nws119) * Comparable:"<=>" * Float,Fixnum:"**" * Array:sort Fri Jan 14 16:53:37 1994 Yukihiro Matsumoto (matz at nws119) * version 0.07 * メソッドに関するドキュメントを充実させた. * String:index(): 引数positionを増やした. Thu Jan 13 15:13:52 1994 Yukihiro Matsumoto (matz at nws119) * 未初期化の変数アクセスをなくした. * 無駄なhash tableのアロケーションを削除. * Purify'd(on Sun) * ~RE と ~STRのコンパイル時展開の抑制. * Sunへ移植. signal()の戻り値. RDataのbug修正. * parse.y: nlsルールを削除. * yylex(): 改行と符合の解析部分を変更. * missing/strftime.c: 移植用. * Time:strftime: その他のメソッドもstrftimeを利用するように. * メソッド再定義時にメソッドキャッシュをクリアする. Fri Jan 7 15:23:20 1994 Yukihiro Matsumoto (matz at nws119) * Float:coerce(): FixnumとFloat以外の引数を与えられるた時には例外 を発生するように. * Stat: stat構造体の全てのメンバに対するアクセスメソッドを用意. * 未定義のクラス/モジュールへの参照がunknownメソッドを呼び出すよう にした. * baseline - version 0.06.
Diffstat (limited to 'bignum.c')
-rw-r--r--bignum.c1121
1 files changed, 1121 insertions, 0 deletions
diff --git a/bignum.c b/bignum.c
new file mode 100644
index 0000000..ce124a6
--- /dev/null
+++ b/bignum.c
@@ -0,0 +1,1121 @@
+/************************************************
+
+ bignum.c -
+
+ $Author: matz $
+ $Date: 1994/06/27 15:48:21 $
+ created at: Fri Jun 10 00:48:55 JST 1994
+
+************************************************/
+
+#include "ruby.h"
+#include <ctype.h>
+
+extern VALUE C_Integer;
+VALUE C_Bignum;
+
+#define BDIGITS(x) RBIGNUM(x)->digits
+#define BITSPERDIG (sizeof(USHORT)*CHAR_BIT)
+#define BIGRAD (1L << BITSPERDIG)
+#define DIGSPERLONG ((UINT)(sizeof(long)/sizeof(USHORT)))
+#define BIGUP(x) ((unsigned long)(x) << BITSPERDIG)
+#define BIGDN(x) ((x) >> BITSPERDIG)
+#define BIGLO(x) ((x) & (BIGRAD-1))
+
+#define MAX(a,b) ((a)>(b)?(a):(b))
+#define MIN(a,b) ((a)<(b)?(a):(b))
+
+static VALUE
+bignew_1(class, len, sign)
+ VALUE class;
+ UINT len;
+ char sign;
+{
+ NEWOBJ(big, struct RBignum);
+ OBJSETUP(big, C_Bignum, T_BIGNUM);
+ big->sign = sign;
+ big->len = len;
+ BDIGITS(big) = ALLOC_N(USHORT, len);
+
+ return (VALUE)big;
+}
+
+#define bignew(len,sign) bignew_1(C_Bignum,len,sign)
+
+static VALUE
+Fbig_new(class, y)
+ VALUE class;
+ struct RBignum *y;
+{
+ Check_Type(y, T_BIGNUM);
+ return bignew_1(class, y->len, y->sign);
+}
+
+VALUE
+Fbig_clone(x)
+ struct RBignum *x;
+{
+ VALUE z = bignew_1(CLASS_OF(x), x->len, x->sign);
+
+ bcopy(BDIGITS(x), BDIGITS(z), x->len*sizeof(USHORT));
+ return (VALUE)z;
+}
+
+void
+big_2comp(x) /* get 2's complement */
+ struct RBignum *x;
+{
+ UINT i = x->len;
+ USHORT *ds = BDIGITS(x);
+ long num;
+
+ while (i--) ds[i] = ~ds[i];
+ i = 0; num = 1;
+ do {
+ num += (long)ds[i];
+ ds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ } while (i < x->len);
+}
+
+VALUE
+bignorm(x)
+ struct RBignum *x;
+{
+ UINT len = x->len;
+ USHORT *ds = BDIGITS(x);
+
+ while (len-- && !ds[len]) ;
+ x->len = ++len;
+ if (len*sizeof(USHORT) <= sizeof(VALUE)) {
+ long num = 0;
+ while (len--) {
+ num = BIGUP(num) + ds[len];
+ }
+ if (x->sign) {
+ if (POSFIXABLE(num)) return INT2FIX(num);
+ }
+ else if (NEGFIXABLE(-num)) return INT2FIX(-num);
+ }
+ return (VALUE)x;
+}
+
+VALUE
+uint2big(n)
+ UINT n;
+{
+ UINT i = 0;
+ USHORT *digits;
+ struct RBignum *big;
+
+ i = 0;
+ big = (struct RBignum*)bignew(DIGSPERLONG, 1);
+ digits = BDIGITS(big);
+ while (i < DIGSPERLONG) {
+ digits[i++] = BIGLO(n);
+ n = BIGDN(n);
+ }
+
+ i = DIGSPERLONG;
+ while (i-- && !digits[i]) ;
+ big->len = i+1;
+ return (VALUE)big;
+}
+
+VALUE
+int2big(n)
+ int n;
+{
+ int neg = 0;
+ struct RBignum *big;
+
+ if (n < 0) {
+ n = -n;
+ neg = 1;
+ }
+ big = (struct RBignum*)uint2big(n);
+ if (neg) {
+ big->sign = FALSE;
+ }
+ return (VALUE)big;
+}
+
+VALUE
+uint2inum(n)
+ UINT n;
+{
+ if (POSFIXABLE(n)) return INT2FIX(n);
+ return uint2big(n);
+}
+
+VALUE
+int2inum(n)
+ int n;
+{
+ if (FIXABLE(n)) return INT2FIX(n);
+ return int2big(n);
+}
+
+VALUE
+str2inum(str, base)
+ char *str;
+ int base;
+{
+ char sign = 1, c;
+ unsigned long num;
+ UINT len, blen = 1, i;
+ VALUE z;
+ USHORT *zds;
+
+ while (isspace(*str)) str++;
+ if (*str == '-') {
+ str++;
+ sign = 0;
+ }
+ if (base == 0) {
+ if (*str == '0') {
+ str++;
+ if (*str == 'x' || *str == 'X') {
+ str++;
+ base = 16;
+ }
+ else {
+ base = 8;
+ }
+ if (*str == '\0') return INT2FIX(0);
+ }
+ else {
+ base = 10;
+ }
+ }
+ len = strlen(str);
+ if (base == 8) {
+ len = 3*len*sizeof(char);
+ }
+ else { /* base == 10 or 16 */
+ len = 4*len*sizeof(char);
+ }
+
+ if (len <= (sizeof(VALUE)*CHAR_BIT)) {
+ int result = strtoul(str, Qnil, base);
+
+ if (!sign) result = -result;
+ if (FIXABLE(result)) return INT2FIX(result);
+ return int2big(result);
+ }
+ len = (len/(sizeof(USHORT)*CHAR_BIT))+1;
+
+ z = bignew(len, sign);
+ zds = BDIGITS(z);
+ for (i=len;i--;) zds[i]=0;
+ while (c = *str++) {
+ switch (c) {
+ case '0': case '1': case '2': case '3': case '4':
+ case '5': case '6': case '7': case '8': case '9':
+ c = c - '0';
+ break;
+ case 'a': case 'b': case 'c':
+ case 'd': case 'e': case 'f':
+ c = c - 'a' + 10;
+ break;
+ case 'A': case 'B': case 'C':
+ case 'D': case 'E': case 'F':
+ c = c - 'A' + 10;
+ break;
+ default:
+ c = base;
+ break;
+ }
+ if (c >= base) break;
+ i = 0;
+ num = c;
+ for (;;) {
+ while (i<blen) {
+ num += zds[i]*base;
+ zds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ }
+ if (num) {
+ blen++;
+ continue;
+ }
+ break;
+ }
+ }
+ return bignorm(z);
+}
+
+static char hexmap[] = "0123456789abcdef";
+VALUE
+big2str(x, base)
+ struct RBignum *x;
+ int base;
+{
+ VALUE t;
+ USHORT *ds;
+ UINT i, j, hbase;
+ VALUE ss;
+ char *s, c;
+
+ if (FIXNUM_P(x)) {
+ return fix2str(x, base);
+ }
+ i = x->len;
+ if (x->len == 0) return str_new2("0");
+ if (base == 10) {
+ j = (sizeof(USHORT)/sizeof(char)*CHAR_BIT*i*241L)/800+2;
+ hbase = 10000;
+ }
+ else if (base == 16) {
+ j = (sizeof(USHORT)/sizeof(char)*CHAR_BIT*i)/4+2;
+ hbase = 0x10000;
+ }
+ else if (base == 8) {
+ j = (sizeof(USHORT)/sizeof(char)*CHAR_BIT*i)+2;
+ hbase = 010000;
+ }
+ else if (base == 2) {
+ j = (sizeof(USHORT)*CHAR_BIT*i)+2;
+ hbase = 020;
+ }
+ else {
+ Fail("bignum cannot treat base %d", base);
+ }
+
+ GC_LINK;
+ GC_PRO3(t, Fbig_clone(x));
+ ds = BDIGITS(t);
+ GC_PRO3(ss, str_new(0, j));
+ s = RSTRING(ss)->ptr;
+
+ s[0] = x->sign ? '+' : '-';
+ while (i && j) {
+ int k = i;
+ unsigned long num = 0;
+ while (k--) {
+ num = BIGUP(num) + ds[k];
+ ds[k] = num / hbase;
+ num %= hbase;
+ }
+ if (ds[i-1] == 0) i--;
+ k = 4;
+ while (k--) {
+ c = num % base;
+ s[--j] = hexmap[(int)c];
+ num /= base;
+ if (i == 0 && num == 0) break;
+ }
+ }
+ while (s[j] == '0') j++;
+ RSTRING(ss)->len -= x->sign?j:j-1;
+ memmove(x->sign?s:s+1, s+j, RSTRING(ss)->len);
+ s[RSTRING(ss)->len] = '\0';
+ GC_UNLINK;
+ return ss;
+}
+
+static VALUE
+Fbig_to_s(x)
+ struct RBignum *x;
+{
+ return big2str(x, 10);
+}
+
+int
+big2int(x)
+ struct RBignum *x;
+{
+ unsigned long num;
+ UINT len = x->len;
+ USHORT *ds;
+
+ if (len > sizeof(long)/sizeof(USHORT))
+ Fail("Bignum too big to convert into fixnum");
+ ds = BDIGITS(x);
+ num = 0;
+ while (len--) {
+ num = BIGUP(num);
+ num += ds[len];
+ }
+ if (!x->sign) return -num;
+ return num;
+}
+
+VALUE
+Fbig_to_i(x)
+ VALUE x;
+{
+ int v = big2int(x);
+
+ if (FIXABLE(v)) {
+ return INT2FIX(v);
+ }
+ return x;
+}
+
+VALUE
+dbl2big(d)
+ double d;
+{
+ UINT i = 0;
+ long c;
+ USHORT *digits;
+ VALUE z;
+ double u = (d < 0)?-d:d;
+
+ while (0 != floor(u)) {
+ u /= BIGRAD;
+ i++;
+ }
+ GC_LINK;
+ GC_PRO3(z, bignew(i, d>=0));
+ digits = BDIGITS(z);
+ while (i--) {
+ u *= BIGRAD;
+ c = floor(u);
+ u -= c;
+ digits[i] = c;
+ }
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+double
+big2dbl(x)
+ struct RBignum *x;
+{
+ double d = 0.0;
+ UINT i = x->len;
+ USHORT *ds = BDIGITS(x);
+
+ while (i--) d = ds[i] + BIGRAD*d;
+ if (!x->sign) d = -d;
+ return d;
+}
+
+VALUE
+Fbig_to_f(x)
+ VALUE x;
+{
+ return float_new(big2dbl(x));
+}
+
+static VALUE
+Fbig_uminus(x)
+ struct RBignum *x;
+{
+ VALUE z = Fbig_clone(x);
+
+ RBIGNUM(z)->sign = !x->sign;
+
+ return bignorm(z);
+}
+
+static VALUE
+bigadd(x, y, sign)
+ struct RBignum *x, *y;
+ char sign;
+{
+ struct RBignum *z;
+ USHORT *zds;
+ long num;
+ UINT i, len;
+
+ len = MAX(x->len, y->len) + 1;
+ z = (struct RBignum*)bignew(len, sign==y->sign);
+ zds = BDIGITS(z);
+
+ i = len;
+ while (i--) zds[i] = 0;
+ i = y->len;
+ while (i--) zds[i] = BDIGITS(y)[i];
+
+ GC_LINK;
+ GC_PRO(z);
+ i = 0; num = 0;
+ if (x->sign == z->sign) {
+ do {
+ num += (long)zds[i] + BDIGITS(x)[i];
+ zds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ } while (i < x->len);
+ if (num) {
+ while (i < y->len) {
+ num += zds[i];
+ zds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ }
+ BDIGITS(z)[i] = num;
+ }
+ }
+ else {
+ do {
+ num += (long)zds[i] - BDIGITS(x)[i];
+ if (num < 0) {
+ zds[i] = num + BIGRAD;
+ num = -1;
+ }
+ else {
+ zds[i] = BIGLO(num);
+ num = 0;
+ }
+ } while (++i < x->len);
+ if (num && x->len == y->len) {
+ num = 1; i = 0;
+ z->sign = 1;
+ do {
+ num += (BIGRAD-1) - zds[i];
+ zds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ } while (i < y->len);
+ }
+ else while (i < y->len) {
+ num += zds[i];
+ if (num < 0) {
+ zds[i++] = num + BIGRAD;
+ num = -1;
+ }
+ else {
+ zds[i++] = BIGLO(num);
+ num = 0;
+ }
+ }
+ }
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+VALUE
+Fbig_plus(x, y)
+ VALUE x, y;
+{
+ VALUE z;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(x, T_BIGNUM);
+ }
+ z = bigadd(x, y, 1);
+ GC_UNLINK;
+ return z;
+}
+
+VALUE
+Fbig_minus(x, y)
+ VALUE x, y;
+{
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+ x = bigadd(x, y, 0);
+ GC_UNLINK;
+
+ return x;
+}
+
+VALUE
+Fbig_mul(x, y)
+ struct RBignum *x, *y;
+{
+ UINT i = 0, j;
+ unsigned long n = 0;
+ VALUE z;
+ USHORT *zds;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = (struct RBignum*)int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ j = x->len + y->len + 1;
+ z = bignew(j, x->sign==y->sign);
+ zds = BDIGITS(z);
+ while (j--) zds[j] = 0;
+ do {
+ j = 0;
+ if (BDIGITS(x)[i]) {
+ do {
+ n += zds[i + j] + ((unsigned long)BDIGITS(x)[i]*BDIGITS(y)[j]);
+ zds[i + j++] = BIGLO(n);
+ n = BIGDN(n);
+ } while (j < y->len);
+ if (n) {
+ zds[i + j] = n;
+ n = 0;
+ }
+ }
+ } while (++i < x->len);
+ GC_UNLINK;
+
+ return bignorm(z);
+}
+
+static void
+bigdivmod(x, y, div, mod)
+ struct RBignum *x, *y;
+ VALUE *div, *mod;
+{
+ UINT nx = x->len, ny = y->len, i, j;
+ VALUE z;
+ USHORT *xds, *yds, *zds, *tds;
+ unsigned long t2;
+ long num;
+ USHORT dd, q;
+
+ yds = BDIGITS(y);
+ if (ny == 0 && yds[0] == 0) Fail("divided by 0");
+ if (nx < ny) {
+ if (div) *div = INT2FIX(0);
+ if (mod) *mod = bignorm(x);
+ return;
+ }
+ xds = BDIGITS(x);
+ if (ny == 1) {
+ dd = yds[0];
+ GC_LINK;
+ GC_PRO3(z, Fbig_clone(x));
+ zds = BDIGITS(z);
+ t2 = 0; i = nx;
+ while(i--) {
+ t2 = BIGUP(t2) + zds[i];
+ zds[i] = t2 / dd;
+ t2 %= dd;
+ }
+ if (div) *div = bignorm(z);
+ if (mod) {
+ if (!y->sign) t2 = -t2;
+ *mod = FIX2INT(t2);
+ }
+ GC_UNLINK;
+ return;
+ }
+ GC_LINK;
+ GC_PRO3(z, bignew(nx==ny?nx+2:nx+1, x->sign==y->sign));
+ zds = BDIGITS(z);
+ if (nx==ny) zds[nx+1] = 0;
+ while (!yds[ny-1]) ny--;
+ if ((dd = BIGRAD/(yds[ny-1]+1)) != 1) {
+ GC_PRO3(y, (struct RBignum*)Fbig_clone(y));
+ tds = BDIGITS(y);
+ j = 0;
+ num = 0;
+ while (j<ny) {
+ num += (unsigned long)yds[j]*dd;
+ tds[j++] = BIGLO(num);
+ num = BIGDN(num);
+ }
+ yds = tds;
+ j = 0;
+ num = 0;
+ while (j<nx) {
+ num += (unsigned long)xds[j]*dd;
+ zds[j++] = BIGLO(num);
+ num = BIGDN(num);
+ }
+ zds[j] = num;
+ }
+ else {
+ zds[nx] = 0;
+ j = nx;
+ while (j--) zds[j] = xds[j];
+ }
+ j = nx==ny?nx+1:nx;
+ do {
+ if (zds[j] == yds[ny-1]) q = BIGRAD-1;
+ else q = (BIGUP(zds[j]) + zds[j-1])/yds[ny-1];
+ if (q) {
+ i = 0; num = 0; t2 = 0;
+ do { /* multiply and subtract */
+ t2 += (unsigned long)yds[i] * q;
+ num += zds[j - ny + i] - BIGLO(t2);
+ if (num < 0) {
+ zds[j - ny + i] = num + BIGRAD;
+ num = -1;
+ }
+ else {
+ zds[j - ny + i] = num;
+ num = 0;
+ }
+ t2 = BIGDN(t2);
+ } while (++i < ny);
+ num += zds[j - ny + i] - t2; /* borrow from high digit; don't update */
+ while (num) { /* "add back" required */
+ i = 0; num = 0; q--;
+ do {
+ num += (long) zds[j - ny + i] + yds[i];
+ zds[j - ny + i] = BIGLO(num);
+ num = BIGDN(num);
+ } while (++i < ny);
+ num--;
+ }
+ }
+ zds[j] = q;
+ } while (--j >= ny);
+ if (div) { /* move quotient down in z */
+ *div = Fbig_clone(z);
+ zds = BDIGITS(*div);
+ j = (nx==ny ? nx+2 : nx+1) - ny;
+ for (i = 0;i < j;i++) zds[i] = zds[i+ny];
+ RBIGNUM(*div)->len = i;
+ *div = bignorm(*div);
+ }
+ if (mod) { /* just normalize remainder */
+ *mod = Fbig_clone(z);
+ if (dd) {
+ zds = BDIGITS(*mod);
+ t2 = 0; i = ny;
+ while(i--) {
+ t2 = BIGUP(t2) + zds[i];
+ zds[i] = t2 / dd;
+ t2 %= dd;
+ }
+ }
+ RBIGNUM(*mod)->len = ny;
+ RBIGNUM(*mod)->sign = y->sign;
+ *mod = bignorm(*mod);
+ }
+ GC_UNLINK;
+}
+
+static VALUE
+Fbig_div(x, y)
+ VALUE x, y;
+{
+ VALUE z;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+ bigdivmod(x, y, &z, Qnil);
+ GC_UNLINK;
+ return z;
+}
+
+static VALUE
+Fbig_mod(x, y)
+ VALUE x, y;
+{
+ VALUE z;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+ bigdivmod(x, y, Qnil, &z);
+ GC_UNLINK;
+ return z;
+}
+
+static VALUE
+Fbig_divmod(x, y)
+ VALUE x, y;
+{
+ VALUE div, mod;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+ bigdivmod(x, y, &div, &mod);
+ GC_UNLINK;
+
+ return assoc_new(div, mod);;
+}
+
+static VALUE
+Fbig_pow(x, y)
+ VALUE x, y;
+{
+ extern double pow();
+ double d1, d2;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ d1 = big2dbl(x);
+ d2 = big2dbl(y);
+ d1 = pow(d1, d2);
+ GC_UNLINK;
+
+ return dbl2big(d1);
+}
+
+VALUE
+Fbig_and(x, y)
+ struct RBignum *x, *y;
+{
+ VALUE z;
+ USHORT *ds1, *ds2, *zds;
+ UINT i, l1, l2;
+ char sign;
+
+ if (FIXNUM_P(y)) {
+ y = (struct RBignum*)int2big(FIX2INT(y));
+ }
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ GC_LINK;
+ GC_PRO(y);
+ if (!y->sign) {
+ y = (struct RBignum*)Fbig_clone(y);
+ big_2comp(y);
+ }
+ if (!x->sign) {
+ GC_PRO3(x, (struct RBignum*)Fbig_clone(x));
+ big_2comp(x);
+ }
+ if (x->len > y->len) {
+ l1 = y->len;
+ l2 = x->len;
+ ds1 = BDIGITS(y);
+ ds2 = BDIGITS(x);
+ sign = y->sign;
+ }
+ else {
+ l1 = x->len;
+ l2 = y->len;
+ ds1 = BDIGITS(x);
+ ds2 = BDIGITS(y);
+ sign = x->sign;
+ }
+ z = bignew(l2, x->sign && y->sign);
+ zds = BDIGITS(z);
+
+ for (i=0; i<l1; i++) {
+ zds[i] = ds1[i] & ds2[i];
+ }
+ for (; i<l2; i++) {
+ zds[i] = sign?0:ds2[i];
+ }
+ if (!RBIGNUM(z)->sign) big_2comp(z);
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+VALUE
+Fbig_or(x, y)
+ struct RBignum *x, *y;
+{
+ VALUE z;
+ USHORT *ds1, *ds2, *zds;
+ UINT i, l1, l2;
+ char sign;
+
+ if (FIXNUM_P(y)) {
+ y = (struct RBignum*)int2big(FIX2INT(y));
+ }
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ GC_LINK;
+ GC_PRO(y);
+ if (!y->sign) {
+ y = (struct RBignum*)Fbig_clone(y);
+ big_2comp(y);
+ }
+ if (!x->sign) {
+ GC_PRO3(x, (struct RBignum*)Fbig_clone(x));
+ big_2comp(x);
+ }
+ if (x->len > y->len) {
+ l1 = y->len;
+ l2 = x->len;
+ ds1 = BDIGITS(y);
+ ds2 = BDIGITS(x);
+ sign = y->sign;
+ }
+ else {
+ l1 = x->len;
+ l2 = y->len;
+ ds1 = BDIGITS(x);
+ ds2 = BDIGITS(y);
+ sign = x->sign;
+ }
+ z = bignew(l2, x->sign || y->sign);
+ zds = BDIGITS(z);
+
+ for (i=0; i<l1; i++) {
+ zds[i] = ds1[i] | ds2[i];
+ }
+ for (; i<l2; i++) {
+ zds[i] = sign?ds2[i]:(BIGRAD-1);
+ }
+ if (!RBIGNUM(z)->sign) big_2comp(z);
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+VALUE
+Fbig_xor(x, y)
+ struct RBignum *x, *y;
+{
+ VALUE z;
+ USHORT *ds1, *ds2, *zds;
+ UINT i, l1, l2;
+ char sign;
+
+ if (FIXNUM_P(y)) {
+ y = (struct RBignum*)int2big(FIX2INT(y));
+ }
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ GC_LINK;
+ GC_PRO(y);
+ if (!y->sign) {
+ y = (struct RBignum*)Fbig_clone(y);
+ big_2comp(y);
+ }
+ if (!x->sign) {
+ GC_PRO3(x, (struct RBignum*)Fbig_clone(x));
+ big_2comp(x);
+ }
+ if (x->len > y->len) {
+ l1 = y->len;
+ l2 = x->len;
+ ds1 = BDIGITS(y);
+ ds2 = BDIGITS(x);
+ sign = y->sign;
+ }
+ else {
+ l1 = x->len;
+ l2 = y->len;
+ ds1 = BDIGITS(x);
+ ds2 = BDIGITS(y);
+ sign = x->sign;
+ }
+ x->sign = x->sign?1:0;
+ y->sign = y->sign?1:0;
+ z = bignew(l2, !(x->sign ^ y->sign));
+ zds = BDIGITS(z);
+
+ for (i=0; i<l1; i++) {
+ zds[i] = ds1[i] ^ ds2[i];
+ }
+ for (; i<l2; i++) {
+ zds[i] = sign?ds2[i]:~ds2[i];
+ }
+ if (!RBIGNUM(z)->sign) big_2comp(z);
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+static VALUE
+Fbig_neg(x)
+ struct RBignum *x;
+{
+ VALUE z = Fbig_clone(x);
+ UINT i = x->len;
+ USHORT *ds = BDIGITS(z);
+
+ if (!x->sign) big_2comp(z);
+ while (i--) ds[i] = ~ds[i];
+ if (x->sign) big_2comp(z);
+ RBIGNUM(z)->sign = !RBIGNUM(z)->sign;
+
+ return bignorm(z);
+}
+
+static VALUE Fbig_rshift();
+
+VALUE
+Fbig_lshift(x, y)
+ struct RBignum *x;
+ VALUE y;
+{
+ USHORT *xds, *zds;
+ UINT shift = NUM2INT(y);
+ UINT s1 = shift/(sizeof(USHORT)*CHAR_BIT);
+ UINT s2 = shift%(sizeof(USHORT)*CHAR_BIT);
+ VALUE z;
+ unsigned long num = 0;
+ UINT len, i;
+
+ if (shift < 0) return Fbig_rshift(x, INT2FIX(-shift));
+ xds = BDIGITS(x);
+ len = x->len;
+ z = bignew(len+s1+1, x->sign);
+ zds = BDIGITS(z);
+ for (i=0; i<s1; i++) {
+ *zds++ = 0;
+ }
+ for (i=0; i<len; i++) {
+ num = num | *xds++<<s2;
+ *zds++ = BIGLO(num);
+ num = BIGDN(num);
+ }
+ *zds = BIGLO(num);
+ return bignorm(z);
+}
+
+static VALUE
+Fbig_rshift(x, y)
+ struct RBignum *x;
+ VALUE y;
+{
+ USHORT *xds, *zds;
+ UINT shift = NUM2INT(y);
+ UINT s1 = shift/(sizeof(USHORT)*CHAR_BIT);
+ UINT s2 = shift%(sizeof(USHORT)*CHAR_BIT);
+ VALUE z;
+ unsigned long num = 0;
+ UINT i = x->len, j;
+
+ if (shift < 0) return Fbig_lshift(x, INT2FIX(-shift));
+ if (s1 > x->len) {
+ if (x->sign)
+ return INT2FIX(0);
+ else
+ return INT2FIX(-1);
+ }
+ xds = BDIGITS(x);
+ i = x->len; j = i - s1;
+ z = bignew(j, x->sign);
+ zds = BDIGITS(z);
+ while (i--, j--) {
+ num = (num | xds[i]) >> s2;
+ zds[j] = BIGLO(num);
+ num = BIGUP(xds[i]);
+ }
+ return bignorm(z);
+}
+
+static VALUE
+Fbig_aref(x, y)
+ struct RBignum *x;
+ VALUE y;
+{
+ USHORT *xds;
+ int shift = NUM2INT(y);
+ UINT s1, s2;
+
+ if (shift < 0) return INT2FIX(0);
+ s1 = shift/(sizeof(USHORT)*CHAR_BIT);
+ s2 = shift%(sizeof(USHORT)*CHAR_BIT);
+
+ if (!x->sign) {
+ if (s1 >= x->len) return INT2FIX(1);
+ x = (struct RBignum*)Fbig_clone(x);
+ big_2comp(x);
+ }
+ else {
+ if (s1 >= x->len) return INT2FIX(0);
+ }
+ xds = BDIGITS(x);
+ if (xds[s1] & (1<<s2))
+ return INT2FIX(1);
+ return INT2FIX(0);
+}
+
+static VALUE
+Fbig_cmp(x, y)
+ struct RBignum *x, *y;
+{
+ int xlen = x->len;
+
+ Check_Type(x, T_BIGNUM);
+ if (x->sign > y->sign) return INT2FIX(1);
+ if (x->sign < y->sign) return INT2FIX(-1);
+ if (xlen < y->len)
+ return (x->sign) ? INT2FIX(-1) : INT2FIX(1);
+ if (xlen > y->len)
+ return (x->sign) ? INT2FIX(1) : INT2FIX(-1);
+
+ while(xlen-- && (BDIGITS(x)[xlen]==BDIGITS(y)[xlen]));
+ if (-1 == xlen) return INT2FIX(0);
+ return (BDIGITS(x)[xlen] < BDIGITS(y)[xlen]) ?
+ (x->sign ? INT2FIX(1) : INT2FIX(-1)) :
+ (x->sign ? INT2FIX(-1) : INT2FIX(1));
+}
+
+static VALUE
+Fbig_hash(x)
+ struct RBignum *x;
+{
+ int i, len, key;
+ USHORT *digits;
+
+ key = 0; digits = BDIGITS(x);
+ for (i=0,len=x->len; i<x->len; i++) {
+ key ^= *digits++;
+ }
+ return INT2FIX(key);
+}
+
+static VALUE
+Fbig_coerce(x, y)
+ struct RBignum *x;
+ VALUE y;
+{
+ if (FIXNUM_P(y)) {
+ return int2big(FIX2INT(y));
+ }
+ else {
+ Fail("can't coerce %s to Bignum", rb_class2name(CLASS_OF(y)));
+ }
+ /* not reached */
+ return Qnil;
+}
+
+static VALUE
+Fbig_abs(x)
+ struct RBignum *x;
+{
+ if (!x->sign) {
+ x = (struct RBignum*)Fbig_clone(x);
+ x->sign = 1;
+ }
+ return (VALUE)x;
+}
+
+Init_Bignum()
+{
+ C_Bignum = rb_define_class("Bignum", C_Integer);
+ rb_define_single_method(C_Bignum, "new", Fbig_new, 1);
+ rb_define_method(C_Bignum, "clone", Fbig_clone, 0);
+ rb_define_method(C_Bignum, "to_s", Fbig_to_s, 0);
+ rb_define_method(C_Bignum, "coerce", Fbig_coerce, 1);
+ rb_define_method(C_Bignum, "-@", Fbig_uminus, 0);
+ rb_define_method(C_Bignum, "+", Fbig_plus, 1);
+ rb_define_method(C_Bignum, "-", Fbig_minus, 1);
+ rb_define_method(C_Bignum, "*", Fbig_mul, 1);
+ rb_define_method(C_Bignum, "/", Fbig_div, 1);
+ rb_define_method(C_Bignum, "%", Fbig_mod, 1);
+ rb_define_method(C_Bignum, "divmod", Fbig_divmod, 1);
+ rb_define_method(C_Bignum, "**", Fbig_pow, 1);
+ rb_define_method(C_Bignum, "&", Fbig_and, 1);
+ rb_define_method(C_Bignum, "|", Fbig_or, 1);
+ rb_define_method(C_Bignum, "^", Fbig_xor, 1);
+ rb_define_method(C_Bignum, "~", Fbig_neg, 0);
+ rb_define_method(C_Bignum, "<<", Fbig_lshift, 1);
+ rb_define_method(C_Bignum, ">>", Fbig_rshift, 1);
+ rb_define_method(C_Bignum, "[]", Fbig_aref, 1);
+
+ rb_define_method(C_Bignum, "<=>", Fbig_cmp, 1);
+ rb_define_method(C_Bignum, "hash", Fbig_hash, 0);
+ rb_define_method(C_Bignum, "to_i", Fbig_to_i, 0);
+ rb_define_method(C_Bignum, "to_f", Fbig_to_f, 0);
+ rb_define_method(C_Bignum, "abs_f", Fbig_abs, 0);
+}