pumpkin/ramp/ll/index.html
2016-05-10 15:03:32 -04:00

519 lines
No EOL
28 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="generator" content="rustdoc">
<meta name="description" content="API documentation for the Rust `ll` mod in crate `ramp`.">
<meta name="keywords" content="rust, rustlang, rust-lang, ll">
<title>ramp::ll - Rust</title>
<link rel="stylesheet" type="text/css" href="../../rustdoc.css">
<link rel="stylesheet" type="text/css" href="../../main.css">
</head>
<body class="rustdoc">
<!--[if lte IE 8]>
<div class="warning">
This old browser is unsupported and will most likely display funky
things.
</div>
<![endif]-->
<nav class="sidebar">
<p class='location'><a href='../index.html'>ramp</a></p><script>window.sidebarCurrent = {name: 'll', ty: 'mod', relpath: '../'};</script><script defer src="../sidebar-items.js"></script>
</nav>
<nav class="sub">
<form class="search-form js-only">
<div class="search-container">
<input class="search-input" name="search"
autocomplete="off"
placeholder="Click or press S to search, ? for more options…"
type="search">
</div>
</form>
</nav>
<section id='main' class="content mod">
<h1 class='fqn'><span class='in-band'>Module <a href='../index.html'>ramp</a>::<wbr><a class='mod' href=''>ll</a></span><span class='out-of-band'><span id='render-detail'>
<a id="toggle-all-docs" href="javascript:void(0)" title="collapse all docs">
[<span class='inner'>&#x2212;</span>]
</a>
</span><a id='src-7' class='srclink' href='../../src/ramp/ll/mod.rs.html#15-736' title='goto source code'>[src]</a></span></h1>
<div class='docblock'><p>This module provides the low-level operations for working with arbitrary precision numbers.</p>
<h2 id='overview' class='section-header'><a href='#overview'>Overview</a></h2>
<p>This module forms the core of the library. As such, the functions are required to be highly
performant, even small inefficiencies can cause a large impact given how frequently some of
these functions are called. <code>addmul</code> for example is one of the most frequently called functions
in the library, so an efficiencies there will be multiplied out to almost the entire library.</p>
<p>There are no real restrictions on the functions that can implemented in here. Exposed functions
should be generally useful to high-level code, but otherwise any operation that can be more
efficiently implemented here and then exposed by a higher-level API is a candidate.</p>
<p>The functions in this module assume that all inputs are valid, though some checking is performed
in debug builds.</p>
<h2 id='limbs' class='section-header'><a href='#limbs'>Limbs</a></h2>
<p>A <code>Limb</code> is a single &quot;digit&quot; in an arbitrary-precision integer. To explain, consider the
standard base we work in, base-10. Base-10 uses represents numbers as a sequence of the digits
0-9. The number 251 is 2 x 10<sup>2</sup> + 5 x 10<sup>1</sup> + 1 x 10<sup>0.</sup> Similarly base-16 (hexadecimal) uses
sixteen digits and a base of 16 to represent numbers.</p>
<p>A <code>Limb</code> is one word, with N bits (32 on a 32-bit platform, 64 on a 64-bit platform), so it can
represent 2<sup>N</sup> unique values. It can therefore form the basis of a base-2<sup>N</sup> number system. The
word &quot;Limb&quot; is used by GMP to distinguish it from a regular numerical digit, and there is no
obvious reason to use different terminology.</p>
<p><code>Limb</code> itself implements a number of useful methods. The basic mathematical operators are
implemented to provide wrapping behaviour by default. The most basic operations are also
implemented on <code>Limb</code>, notably multiplication with a two-word output and division of a two-word
numerator by a one-word denominator. The implementations of these operations are done with
inline assembly on x86 platforms with a Rust implementation as fallback.</p>
<h2 id='integer-representation' class='section-header'><a href='#integer-representation'>Integer representation</a></h2>
<p>Integers are passed around as pointers to a series of <code>Limb</code>s. The limbs are stored
least-significant first. If required, a size parameter is also provided, but otherwise is
omitted when it can be inferred from other sources of information. This is the case with the
output pointers used to store the result, they are assumed to have enough memory store the
result as the maximum output size is bounded by the size of the inputs.</p>
<p>The integers are not required to be &quot;normalized&quot; in most cases. That is, they may have
zero-value limbs in the highest positions. Functions should aim to avoid requiring normalized
integers but otherwise explicitly document said requirement.</p>
<h2 id='memory-allocation' class='section-header'><a href='#memory-allocation'>Memory allocation</a></h2>
<p>No function will allocate memory for a return value. However, it is sometimes required to
allocate &quot;scratch space&quot; for storing intermediate values. This scratch space is always temporary
and freed before the function returns. Functions that need to make heavy use of scratch space
while also being recursive, are split so that scratch space can be re-used.</p>
<h2 id='argument-conventions' class='section-header'><a href='#argument-conventions'>Argument Conventions</a></h2>
<p>There are no hard-and-fast rules for the argument conventions in this module. There are however
some general conventions:</p>
<ul>
<li>Output/Result pointer goes first (if applicable).</li>
<li>Pointer and matching size are kept close together in the argument list.</li>
<li>Sizes come after the matching pointers. For example, <code>add_n</code> takes two pointers and a length,
the length applies to both pointers and so comes after both of them.</li>
</ul>
</div><h2 id='modules' class='section-header'><a href="#modules">Modules</a></h2>
<table>
<tr class=' module-item'>
<td><a class='mod' href='base/index.html'
title='ramp::ll::base'>base</a></td>
<td class='docblock short'>
<p>Base conversion utilities</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='mod' href='limb/index.html'
title='ramp::ll::limb'>limb</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='mod' href='limb_ptr/index.html'
title='ramp::ll::limb_ptr'>limb_ptr</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='mod' href='pow/index.html'
title='ramp::ll::pow'>pow</a></td>
<td class='docblock short'>
</td>
</tr></table><h2 id='functions' class='section-header'><a href="#functions">Functions</a></h2>
<table>
<tr class=' module-item'>
<td><a class='fn' href='fn.add.html'
title='ramp::ll::add'>add</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.add_1.html'
title='ramp::ll::add_1'>add_1</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.add_n.html'
title='ramp::ll::add_n'>add_n</a></td>
<td class='docblock short'>
<p>Adds the <code>n</code> least signficant limbs of <code>xp</code> and <code>yp</code>, storing the result in {wp, n}.
If there was a carry, it is returned.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.addmul_1.html'
title='ramp::ll::addmul_1'>addmul_1</a></td>
<td class='docblock short'>
<p>Multiplies the <code>n</code> least-signficiant digits of <code>xp</code> by <code>vl</code> and adds them to the <code>n</code>
least-significant digits of <code>wp</code>. Returns the highest limb of the result.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.and_n.html'
title='ramp::ll::and_n'>and_n</a></td>
<td class='docblock short'>
<p>Performs a bitwise &quot;and&quot; (<code>&amp;</code>) of the n least signficant limbs of <code>xp</code> and <code>yp</code>, storing the
result in <code>wp</code></p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.and_not_n.html'
title='ramp::ll::and_not_n'>and_not_n</a></td>
<td class='docblock short'>
<p>Performs a bitwise and of the n least signficant limbs of <code>xp</code> and <code>yp</code>, with the limbs of <code>yp</code>
being first inverted. The result is stored in <code>wp</code>.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.cmp.html'
title='ramp::ll::cmp'>cmp</a></td>
<td class='docblock short'>
<p>Compares the <code>n</code> least-significant limbs of <code>xp</code> and <code>yp</code>, returning whether
{xp, n} is less than, equal to or greater than {yp, n}</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.copy_decr.html'
title='ramp::ll::copy_decr'>copy_decr</a></td>
<td class='docblock short'>
<p>Copies the <code>n</code> limbs from <code>src</code> to <code>dst</code> in a decremental fashion.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.copy_incr.html'
title='ramp::ll::copy_incr'>copy_incr</a></td>
<td class='docblock short'>
<p>Copies the <code>n</code> limbs from <code>src</code> to <code>dst</code> in an incremental fashion.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.copy_rest.html'
title='ramp::ll::copy_rest'>copy_rest</a></td>
<td class='docblock short'>
<p>Copies the <code>n - start</code> limbs from <code>src + start</code> to <code>dst + start</code></p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.decr.html'
title='ramp::ll::decr'>decr</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.divide_by_zero.html'
title='ramp::ll::divide_by_zero'>divide_by_zero</a></td>
<td class='docblock short'>
<p>Called when a divide by zero occurs.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.divrem.html'
title='ramp::ll::divrem'>divrem</a></td>
<td class='docblock short'>
<p>Divides {np, ns} by {dp, ds}. If ns &lt;= ds, the quotient is stored in {qp, 1}, otherwise
the quotient is stored to {qp, (ns - ds) + 1}. The remainder is always stored to {rp, ds}.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.divrem_1.html'
title='ramp::ll::divrem_1'>divrem_1</a></td>
<td class='docblock short'>
<p>Divides the <code>xs</code> least-significant limbs at <code>xp</code> by <code>d</code>, storing the result in {qp, qxn + xs}.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.divrem_2.html'
title='ramp::ll::divrem_2'>divrem_2</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.gcd.html'
title='ramp::ll::gcd'>gcd</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.incr.html'
title='ramp::ll::incr'>incr</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.is_zero.html'
title='ramp::ll::is_zero'>is_zero</a></td>
<td class='docblock short'>
<p>Checks that all <code>nn</code> limbs in <code>np</code> are zero</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.mul.html'
title='ramp::ll::mul'>mul</a></td>
<td class='docblock short'>
<p>Multiplies <code>{xp, xs}</code> by <code>{yp, ys}</code>, storing the result to <code>{wp, xs + ys}</code>.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.mul_1.html'
title='ramp::ll::mul_1'>mul_1</a></td>
<td class='docblock short'>
<p>Multiplies the <code>n</code> least-significant limbs of <code>xp</code> by <code>vl</code> storing the <code>n</code> least-significant
limbs of the product in <code>{wp, n}</code>.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.nand_n.html'
title='ramp::ll::nand_n'>nand_n</a></td>
<td class='docblock short'>
<p>Performs a bitwise &quot;nand&quot; of the n least signficant limbs of <code>xp</code> and <code>yp</code>, storing the
result in <code>wp</code></p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.nor_n.html'
title='ramp::ll::nor_n'>nor_n</a></td>
<td class='docblock short'>
<p>Performs a bitwise &quot;nor&quot; of the n least signficant limbs of <code>xp</code> and <code>yp</code>, storing the
result in <code>wp</code></p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.normalize.html'
title='ramp::ll::normalize'>normalize</a></td>
<td class='docblock short'>
<p>Returns the size of the integer pointed to by <code>p</code> such that the most
significant limb is non-zero.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.not.html'
title='ramp::ll::not'>not</a></td>
<td class='docblock short'>
<p>Performs a bitwise inversion (&quot;not&quot;) of the n least signficant limbs of <code>xp</code>, storing the
result in <code>wp</code></p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.or_n.html'
title='ramp::ll::or_n'>or_n</a></td>
<td class='docblock short'>
<p>Performs a bitwise &quot;or&quot; (<code>|</code>) of the n least signficant limbs of <code>xp</code> and <code>yp</code>, storing the
result in <code>wp</code></p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.or_not_n.html'
title='ramp::ll::or_not_n'>or_not_n</a></td>
<td class='docblock short'>
<p>Performs a bitwise &quot;or&quot; of the n least signficant limbs of <code>xp</code> and <code>yp</code>, with the limbs of <code>yp</code>
being first inverted. The result is stored in <code>wp</code>.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.overlap.html'
title='ramp::ll::overlap'>overlap</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.same_or_decr.html'
title='ramp::ll::same_or_decr'>same_or_decr</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.same_or_incr.html'
title='ramp::ll::same_or_incr'>same_or_incr</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.same_or_separate.html'
title='ramp::ll::same_or_separate'>same_or_separate</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.scan_0.html'
title='ramp::ll::scan_0'>scan_0</a></td>
<td class='docblock short'>
<p>Scans for the first 0 bit starting from the least-significant bit the the most, returning
the bit index.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.scan_1.html'
title='ramp::ll::scan_1'>scan_1</a></td>
<td class='docblock short'>
<p>Scans for the first 1 bit starting from the least-significant bit the the most, returning
the bit index.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.shl.html'
title='ramp::ll::shl'>shl</a></td>
<td class='docblock short'>
<p>Performs a bit-shift of the limbs in {xp, xs}, left by <code>cnt</code> bits storing the result in {rp,
rs}. The top-most shifted bits are returned.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.shr.html'
title='ramp::ll::shr'>shr</a></td>
<td class='docblock short'>
<p>Performs a bit-shift of the limbs in {xp, xs}, right by <code>cnt</code> bits storing the result in {rp,
rs}. The bottom-most shifted bits are returned.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.sqr.html'
title='ramp::ll::sqr'>sqr</a></td>
<td class='docblock short'>
<p>Squares the number in <code>{xp, xs}</code> storing the result in <code>{wp, xs*2}</code>.
This is slightly more efficient than regular multiplication with both
inputs the same.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.sub.html'
title='ramp::ll::sub'>sub</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.sub_1.html'
title='ramp::ll::sub_1'>sub_1</a></td>
<td class='docblock short'>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.sub_n.html'
title='ramp::ll::sub_n'>sub_n</a></td>
<td class='docblock short'>
<p>Subtracts the <code>n</code> least signficant limbs of <code>yp</code> from <code>xp</code>, storing the result in {wp, n}.
If there was a borrow from a higher-limb (i.e., the result would be negative), it is returned.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.submul_1.html'
title='ramp::ll::submul_1'>submul_1</a></td>
<td class='docblock short'>
<p>Multiplies the <code>n</code> least-signficiant digits of <code>xp</code> by <code>vl</code> and subtracts them from the <code>n</code>
least-significant digits of <code>wp</code>. Returns the highest limb of the result, adjust for borrow.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.twos_complement.html'
title='ramp::ll::twos_complement'>twos_complement</a></td>
<td class='docblock short'>
<p>Computes the two&#39;s complement of the <code>xs</code> least significant words
of <code>xp</code>. The result is stored the result in <code>wp</code>, and a carry is
returned, if there is one.</p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.xor_n.html'
title='ramp::ll::xor_n'>xor_n</a></td>
<td class='docblock short'>
<p>Performs a bitwise &quot;xor&quot; (<code>^</code>) of the n least signficant limbs of <code>xp</code> and <code>yp</code>, storing the
result in <code>wp</code></p>
</td>
</tr>
<tr class=' module-item'>
<td><a class='fn' href='fn.zero.html'
title='ramp::ll::zero'>zero</a></td>
<td class='docblock short'>
</td>
</tr></table></section>
<section id='search' class="content hidden"></section>
<section class="footer"></section>
<aside id="help" class="hidden">
<div>
<h1 class="hidden">Help</h1>
<div class="shortcuts">
<h2>Keyboard Shortcuts</h2>
<dl>
<dt>?</dt>
<dd>Show this help dialog</dd>
<dt>S</dt>
<dd>Focus the search field</dd>
<dt>&larrb;</dt>
<dd>Move up in search results</dd>
<dt>&rarrb;</dt>
<dd>Move down in search results</dd>
<dt>&#9166;</dt>
<dd>Go to active search result</dd>
</dl>
</div>
<div class="infos">
<h2>Search Tricks</h2>
<p>
Prefix searches with a type followed by a colon (e.g.
<code>fn:</code>) to restrict the search to a given type.
</p>
<p>
Accepted types are: <code>fn</code>, <code>mod</code>,
<code>struct</code>, <code>enum</code>,
<code>trait</code>, <code>type</code>, <code>macro</code>,
and <code>const</code>.
</p>
<p>
Search functions by type signature (e.g.
<code>vec -> usize</code> or <code>* -> vec</code>)
</p>
</div>
</div>
</aside>
<script>
window.rootPath = "../../";
window.currentCrate = "ramp";
window.playgroundUrl = "";
</script>
<script src="../../jquery.js"></script>
<script src="../../main.js"></script>
<script defer src="../../search-index.js"></script>
</body>
</html>