Google Git
Sign in
apache / incubator-teaclave-website / refs/heads/asf-site / . / api-docs / crates-enclave / src / fastdivide / lib.rs.html
blob: 5474f44858692d890cabddf361c35b463e8b390a [file] [log] [blame]
<!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="Source of the Rust file `/root/.cargo/registry/src/github.com-1ecc6299db9ec823/fastdivide-0.4.0/src/lib.rs`."><meta name="keywords" content="rust, rustlang, rust-lang"><title>lib.rs - source</title><link rel="preload" as="font" type="font/woff2" crossorigin href="../../SourceSerif4-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../FiraSans-Regular.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../FiraSans-Medium.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../SourceCodePro-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../SourceSerif4-Bold.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../SourceCodePro-Semibold.ttf.woff2"><link rel="stylesheet" href="../../normalize.css"><link rel="stylesheet" href="../../rustdoc.css" id="mainThemeStyle"><link rel="stylesheet" href="../../ayu.css" disabled><link rel="stylesheet" href="../../dark.css" disabled><link rel="stylesheet" href="../../light.css" id="themeStyle"><script id="default-settings" ></script><script src="../../storage.js"></script><script defer src="../../source-script.js"></script><script defer src="../../source-files.js"></script><script defer src="../../main.js"></script><noscript><link rel="stylesheet" href="../../noscript.css"></noscript><link rel="alternate icon" type="image/png" href="../../favicon-16x16.png"><link rel="alternate icon" type="image/png" href="../../favicon-32x32.png"><link rel="icon" type="image/svg+xml" href="../../favicon.svg"></head><body class="rustdoc source"><!--[if lte IE 11]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><nav class="sidebar"><a class="sidebar-logo" href="../../fastdivide/index.html"><div class="logo-container"><img class="rust-logo" src="../../rust-logo.svg" alt="logo"></div></a></nav><main><div class="width-limiter"><nav class="sub"><a class="sub-logo-container" href="../../fastdivide/index.html"><img class="rust-logo" src="../../rust-logo.svg" alt="logo"></a><form class="search-form"><div class="search-container"><span></span><input class="search-input" name="search" autocomplete="off" spellcheck="false" placeholder="Click or press ‘S’ to search, ‘?’ for more options…" type="search"><div id="help-button" title="help" tabindex="-1"><a href="../../help.html">?</a></div><div id="settings-menu" tabindex="-1"><a href="../../settings.html" title="settings"><img width="22" height="22" alt="Change settings" src="../../wheel.svg"></a></div></div></form></nav><section id="main-content" class="content"><div class="example-wrap"><pre class="src-line-numbers"><span id="1">1</span>
<span id="2">2</span>
<span id="3">3</span>
<span id="4">4</span>
<span id="5">5</span>
<span id="6">6</span>
<span id="7">7</span>
<span id="8">8</span>
<span id="9">9</span>
<span id="10">10</span>
<span id="11">11</span>
<span id="12">12</span>
<span id="13">13</span>
<span id="14">14</span>
<span id="15">15</span>
<span id="16">16</span>
<span id="17">17</span>
<span id="18">18</span>
<span id="19">19</span>
<span id="20">20</span>
<span id="21">21</span>
<span id="22">22</span>
<span id="23">23</span>
<span id="24">24</span>
<span id="25">25</span>
<span id="26">26</span>
<span id="27">27</span>
<span id="28">28</span>
<span id="29">29</span>
<span id="30">30</span>
<span id="31">31</span>
<span id="32">32</span>
<span id="33">33</span>
<span id="34">34</span>
<span id="35">35</span>
<span id="36">36</span>
<span id="37">37</span>
<span id="38">38</span>
<span id="39">39</span>
<span id="40">40</span>
<span id="41">41</span>
<span id="42">42</span>
<span id="43">43</span>
<span id="44">44</span>
<span id="45">45</span>
<span id="46">46</span>
<span id="47">47</span>
<span id="48">48</span>
<span id="49">49</span>
<span id="50">50</span>
<span id="51">51</span>
<span id="52">52</span>
<span id="53">53</span>
<span id="54">54</span>
<span id="55">55</span>
<span id="56">56</span>
<span id="57">57</span>
<span id="58">58</span>
<span id="59">59</span>
<span id="60">60</span>
<span id="61">61</span>
<span id="62">62</span>
<span id="63">63</span>
<span id="64">64</span>
<span id="65">65</span>
<span id="66">66</span>
<span id="67">67</span>
<span id="68">68</span>
<span id="69">69</span>
<span id="70">70</span>
<span id="71">71</span>
<span id="72">72</span>
<span id="73">73</span>
<span id="74">74</span>
<span id="75">75</span>
<span id="76">76</span>
<span id="77">77</span>
<span id="78">78</span>
<span id="79">79</span>
<span id="80">80</span>
<span id="81">81</span>
<span id="82">82</span>
<span id="83">83</span>
<span id="84">84</span>
<span id="85">85</span>
<span id="86">86</span>
<span id="87">87</span>
<span id="88">88</span>
<span id="89">89</span>
<span id="90">90</span>
<span id="91">91</span>
<span id="92">92</span>
<span id="93">93</span>
<span id="94">94</span>
<span id="95">95</span>
<span id="96">96</span>
<span id="97">97</span>
<span id="98">98</span>
<span id="99">99</span>
<span id="100">100</span>
<span id="101">101</span>
<span id="102">102</span>
<span id="103">103</span>
<span id="104">104</span>
<span id="105">105</span>
<span id="106">106</span>
<span id="107">107</span>
<span id="108">108</span>
<span id="109">109</span>
<span id="110">110</span>
<span id="111">111</span>
<span id="112">112</span>
<span id="113">113</span>
<span id="114">114</span>
<span id="115">115</span>
<span id="116">116</span>
<span id="117">117</span>
<span id="118">118</span>
<span id="119">119</span>
<span id="120">120</span>
<span id="121">121</span>
<span id="122">122</span>
<span id="123">123</span>
<span id="124">124</span>
<span id="125">125</span>
<span id="126">126</span>
<span id="127">127</span>
<span id="128">128</span>
<span id="129">129</span>
<span id="130">130</span>
<span id="131">131</span>
<span id="132">132</span>
<span id="133">133</span>
<span id="134">134</span>
<span id="135">135</span>
<span id="136">136</span>
<span id="137">137</span>
<span id="138">138</span>
<span id="139">139</span>
<span id="140">140</span>
<span id="141">141</span>
<span id="142">142</span>
<span id="143">143</span>
<span id="144">144</span>
<span id="145">145</span>
<span id="146">146</span>
<span id="147">147</span>
<span id="148">148</span>
<span id="149">149</span>
<span id="150">150</span>
<span id="151">151</span>
<span id="152">152</span>
<span id="153">153</span>
<span id="154">154</span>
<span id="155">155</span>
<span id="156">156</span>
<span id="157">157</span>
<span id="158">158</span>
<span id="159">159</span>
<span id="160">160</span>
<span id="161">161</span>
<span id="162">162</span>
<span id="163">163</span>
<span id="164">164</span>
<span id="165">165</span>
<span id="166">166</span>
<span id="167">167</span>
<span id="168">168</span>
<span id="169">169</span>
<span id="170">170</span>
<span id="171">171</span>
<span id="172">172</span>
<span id="173">173</span>
<span id="174">174</span>
<span id="175">175</span>
<span id="176">176</span>
<span id="177">177</span>
<span id="178">178</span>
<span id="179">179</span>
<span id="180">180</span>
<span id="181">181</span>
<span id="182">182</span>
<span id="183">183</span>
<span id="184">184</span>
<span id="185">185</span>
<span id="186">186</span>
<span id="187">187</span>
<span id="188">188</span>
<span id="189">189</span>
<span id="190">190</span>
<span id="191">191</span>
<span id="192">192</span>
<span id="193">193</span>
<span id="194">194</span>
<span id="195">195</span>
<span id="196">196</span>
<span id="197">197</span>
<span id="198">198</span>
<span id="199">199</span>
<span id="200">200</span>
<span id="201">201</span>
<span id="202">202</span>
<span id="203">203</span>
<span id="204">204</span>
<span id="205">205</span>
<span id="206">206</span>
<span id="207">207</span>
<span id="208">208</span>
<span id="209">209</span>
<span id="210">210</span>
<span id="211">211</span>
<span id="212">212</span>
<span id="213">213</span>
<span id="214">214</span>
<span id="215">215</span>
<span id="216">216</span>
<span id="217">217</span>
<span id="218">218</span>
<span id="219">219</span>
<span id="220">220</span>
<span id="221">221</span>
<span id="222">222</span>
<span id="223">223</span>
<span id="224">224</span>
<span id="225">225</span>
<span id="226">226</span>
<span id="227">227</span>
<span id="228">228</span>
<span id="229">229</span>
<span id="230">230</span>
<span id="231">231</span>
<span id="232">232</span>
<span id="233">233</span>
<span id="234">234</span>
<span id="235">235</span>
<span id="236">236</span>
<span id="237">237</span>
<span id="238">238</span>
<span id="239">239</span>
<span id="240">240</span>
<span id="241">241</span>
<span id="242">242</span>
<span id="243">243</span>
<span id="244">244</span>
<span id="245">245</span>
<span id="246">246</span>
<span id="247">247</span>
<span id="248">248</span>
<span id="249">249</span>
<span id="250">250</span>
</pre><pre class="rust"><code><span class="doccomment">/*!
# Yes, but what is it really ?
Division is a very costly operation for your CPU (probably between 10
and 40 cycles).
You may have noticed that when the divisor is known at compile time,
your compiler transforms the operations into a cryptic combination of
a multiplication and bitshift.
Fastdivide is about doing the same trick your compiler uses but
when the divisor is unknown at compile time.
Of course, it requires preprocessing a datastructure that is
specific to your divisor, and using it only makes sense if
this preprocessing is amortized by a high number of division (with the
same divisor).
# When is it useful ?
You should probably use `fastdivide`, if you do a lot (&gt; 10) of division with the same divisor ;
and these divisions are a bottleneck in your program.
This is for instance useful to compute histograms.
# Example
```rust
use fastdivide::DividerU64;
fn histogram(vals: &amp;[u64], min: u64, interval: u64, output: &amp;mut [usize]) {
// Preprocessing a datastructure dedicated
// to dividing `u64` by `interval`.
//
// This preprocessing is not cheap.
let divide = DividerU64::divide_by(interval);
// We reuse the same `Divider` for all of the
// values in vals.
for &amp;val in vals {
if val &lt; min {
continue;
}
let bucket_id = divide.divide(val - min) as usize;
if bucket_id &lt; output.len() {
output[bucket_id as usize] += 1;
}
}
}
# let mut output = vec![0; 3];
# histogram(&amp;[0u64, 1u64, 4u64, 36u64, 2u64, 1u64], 1u64, 3u64, &amp;mut output[..]);
# assert_eq!(output[0], 3);
# assert_eq!(output[1], 1);
# assert_eq!(output[2], 0);
```
*/
</span><span class="attribute">#![no_std]
#[cfg(feature = <span class="string">&quot;std&quot;</span>)]
</span><span class="kw">extern crate </span>std;
<span class="attribute">#[cfg(test)]
#[macro_use]
</span><span class="kw">extern crate </span>std;
<span class="comment">// ported from libdivide.h by ridiculous_fish
//
// This file is not the original library, it is an attempt to port part
// of it to rust.
// This algorithm is described in https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html
</span><span class="attribute">#[derive(Debug, Clone, Copy, PartialEq, Eq)]
</span><span class="kw">pub enum </span>DividerU64 {
Fast { magic: u64, shift: u8 },
BitShift(u8),
General { magic_low: u64, shift: u8 },
}
<span class="attribute">#[inline(always)]
</span><span class="kw">fn </span>libdivide_mullhi_u64(x: u64, y: u64) -&gt; u64 {
<span class="kw">let </span>xl = x <span class="kw">as </span>u128;
<span class="kw">let </span>yl = y <span class="kw">as </span>u128;
((xl * yl) &gt;&gt; <span class="number">64</span>) <span class="kw">as </span>u64
}
<span class="attribute">#[inline(always)]
</span><span class="kw">fn </span>is_power_of_2(n: u64) -&gt; bool {
n &amp; (n - <span class="number">1</span>) == <span class="number">0
</span>}
<span class="kw">impl </span>DividerU64 {
<span class="kw">fn </span>power_of_2_division(divisor: u64) -&gt; <span class="prelude-ty">Option</span>&lt;DividerU64&gt; {
<span class="kw">let </span>floor_log_2_d: u8 = <span class="number">63u8 </span>- (divisor.leading_zeros() <span class="kw">as </span>u8);
<span class="kw">if </span>is_power_of_2(divisor) {
<span class="comment">// Divisor is a power of 2.
// We can just do a bit shift.
</span><span class="kw">return </span><span class="prelude-val">Some</span>(DividerU64::BitShift(floor_log_2_d));
}
<span class="prelude-val">None
</span>}
<span class="kw">fn </span>fast_path(divisor: u64) -&gt; <span class="prelude-ty">Option</span>&lt;DividerU64&gt; {
<span class="kw">if </span>is_power_of_2(divisor) {
<span class="kw">return </span><span class="prelude-val">None</span>;
}
<span class="kw">let </span>floor_log_2_d: u8 = <span class="number">63u8 </span>- (divisor.leading_zeros() <span class="kw">as </span>u8);
<span class="kw">let </span>u = <span class="number">1u128 </span>&lt;&lt; (floor_log_2_d + <span class="number">64</span>);
<span class="kw">let </span>proposed_magic_number: u128 = u / divisor <span class="kw">as </span>u128;
<span class="kw">let </span>reminder: u64 = (u - proposed_magic_number * (divisor <span class="kw">as </span>u128)) <span class="kw">as </span>u64;
<span class="macro">assert!</span>(reminder &gt; <span class="number">0 </span>&amp;&amp; reminder &lt; divisor);
<span class="kw">let </span>e: u64 = divisor - reminder;
<span class="comment">// This is a sufficient condition for our 64-bits magic number
// condition to work as described in
// See https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html
</span><span class="kw">if </span>e &gt;= (<span class="number">1u64 </span>&lt;&lt; floor_log_2_d) {
<span class="kw">return </span><span class="prelude-val">None</span>;
}
<span class="prelude-val">Some</span>(DividerU64::Fast {
magic: (proposed_magic_number <span class="kw">as </span>u64) + <span class="number">1u64</span>,
shift: floor_log_2_d,
})
}
<span class="kw">fn </span>general_path(divisor: u64) -&gt; DividerU64 {
<span class="macro">assert!</span>(!is_power_of_2(divisor));
<span class="comment">// p=⌈log2d⌉
</span><span class="kw">let </span>p: u8 = <span class="number">64u8 </span>- (divisor.leading_zeros() <span class="kw">as </span>u8);
<span class="comment">// m=⌈2^{64+p} / d⌉. This is a 33 bit number, so keep only the low 32 bits.
// we do a little dance to avoid the overflow if p = 64.
</span><span class="kw">let </span>e = <span class="number">1u128 </span>&lt;&lt; (<span class="number">63 </span>+ p);
<span class="kw">let </span>m = <span class="number">2 </span>+ (e + (e - divisor <span class="kw">as </span>u128)) / divisor <span class="kw">as </span>u128;
DividerU64::General {
magic_low: m <span class="kw">as </span>u64,
shift: p - <span class="number">1</span>,
}
}
<span class="kw">pub fn </span>divide_by(divisor: u64) -&gt; DividerU64 {
<span class="macro">assert!</span>(divisor &gt; <span class="number">0u64</span>);
<span class="self">Self</span>::power_of_2_division(divisor)
.or_else(|| DividerU64::fast_path(divisor))
.unwrap_or_else(|| DividerU64::general_path(divisor))
}
<span class="attribute">#[inline(always)]
</span><span class="kw">pub fn </span>divide(<span class="kw-2">&amp;</span><span class="self">self</span>, n: u64) -&gt; u64 {
<span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{
DividerU64::BitShift(d) =&gt; n &gt;&gt; d,
DividerU64::Fast { magic, shift } =&gt; {
<span class="comment">// The divisor has a magic number that is lower than 32 bits.
// We get away with a multiplication and a bit-shift.
</span>libdivide_mullhi_u64(magic, n) &gt;&gt; shift
}
DividerU64::General { magic_low, shift } =&gt; {
<span class="comment">// magic only contains the low 64 bits of our actual magic number which actually has a 65 bits.
// The following dance computes n * (magic + 2^64) &gt;&gt; shift
</span><span class="kw">let </span>q = libdivide_mullhi_u64(magic_low, n);
<span class="kw">let </span>t = ((n - q) &gt;&gt; <span class="number">1</span>).wrapping_add(q);
t &gt;&gt; shift
}
}
}
}
<span class="attribute">#[cfg(test)]
</span><span class="kw">mod </span>tests {
<span class="kw">use </span><span class="kw">super</span>::DividerU64;
<span class="kw">use </span>proptest::prelude::<span class="kw-2">*</span>;
<span class="attribute">#[test]
</span><span class="kw">fn </span>test_divide_by_4() {
<span class="kw">let </span>divider = DividerU64::divide_by(<span class="number">4</span>);
<span class="macro">assert!</span>(<span class="macro">matches!</span>(divider, DividerU64::BitShift(<span class="number">2</span>)));
}
<span class="attribute">#[test]
</span><span class="kw">fn </span>test_divide_by_7() {
<span class="kw">let </span>divider = DividerU64::divide_by(<span class="number">7</span>);
<span class="macro">assert!</span>(<span class="macro">matches!</span>(divider, DividerU64::General { .. }));
}
<span class="attribute">#[test]
</span><span class="kw">fn </span>test_divide_by_11() {
<span class="kw">let </span>divider = DividerU64::divide_by(<span class="number">11</span>);
<span class="macro">assert_eq!</span>(
divider,
DividerU64::Fast {
magic: <span class="number">13415813871788764812</span>,
shift: <span class="number">3
</span>}
);
}
<span class="macro">proptest! </span>{
<span class="attribute">#![proptest_config(ProptestConfig::with_cases(<span class="number">100000</span>))]
#[test]
</span><span class="kw">fn </span>test_proptest(n <span class="kw">in </span><span class="number">0</span>..u64::MAX, d <span class="kw">in </span><span class="number">1</span>..u64::MAX) {
<span class="kw">let </span>divider = DividerU64::divide_by(d);
<span class="kw">let </span>quotient = divider.divide(n);
<span class="macro">assert_eq!</span>(quotient, n / d);
}
}
<span class="macro">proptest! </span>{
<span class="attribute">#![proptest_config(ProptestConfig::with_cases(<span class="number">100000</span>))]
#[test]
</span><span class="kw">fn </span>test_proptest_divide_by_7(n <span class="kw">in </span><span class="number">0</span>..u64::MAX) {
<span class="kw">let </span>divider = DividerU64::divide_by(<span class="number">7</span>);
<span class="kw">let </span>quotient = divider.divide(n);
<span class="macro">assert_eq!</span>(quotient, n / <span class="number">7</span>);
}
}
<span class="macro">proptest! </span>{
<span class="attribute">#![proptest_config(ProptestConfig::with_cases(<span class="number">10000</span>))]
#[test]
</span><span class="kw">fn </span>test_proptest_divide_by_11(n <span class="kw">in </span><span class="number">0</span>..u64::MAX) {
<span class="kw">let </span>divider = DividerU64::divide_by(<span class="number">11</span>);
<span class="kw">let </span>quotient = divider.divide(n);
<span class="macro">assert_eq!</span>(quotient, n / <span class="number">11</span>);
}
}
<span class="macro">proptest! </span>{
<span class="attribute">#![proptest_config(ProptestConfig::with_cases(<span class="number">10000</span>))]
#[test]
</span><span class="kw">fn </span>test_proptest_divide_by_any(d <span class="kw">in </span><span class="number">1</span>..u64::MAX) {
DividerU64::divide_by(d);
}
}
<span class="attribute">#[test]
</span><span class="kw">fn </span>test_libdivide() {
<span class="kw">for </span>d <span class="kw">in </span>(<span class="number">1u64</span>..<span class="number">100u64</span>)
.chain(<span class="macro">vec!</span>[<span class="number">2048</span>, <span class="number">234234131223u64</span>].into_iter())
.chain((<span class="number">5</span>..<span class="number">63</span>).map(|i| <span class="number">1 </span>&lt;&lt; i))
{
<span class="kw">let </span>divider = DividerU64::divide_by(d);
<span class="kw">for </span>i <span class="kw">in </span>(<span class="number">0u64</span>..<span class="number">10_000</span>).chain(<span class="macro">vec!</span>[<span class="number">2048</span>, <span class="number">234234131223u64</span>, <span class="number">1 </span>&lt;&lt; <span class="number">43</span>, <span class="number">1 </span>&lt;&lt; <span class="number">43 </span>+ <span class="number">1</span>]) {
<span class="macro">assert_eq!</span>(divider.divide(i), i / d);
}
}
}
}
</code></pre></div>
</section></div></main><div id="rustdoc-vars" data-root-path="../../" data-current-crate="fastdivide" data-themes="ayu,dark,light" data-resource-suffix="" data-rustdoc-version="1.66.0-nightly (5c8bff74b 2022-10-21)" ></div></body></html>