AV1 specification を読む 2018-04-17 (7.10.2.6. Resolve Divisor Process)

#AV1 specification 日本語訳 (2018-04-17)

Resolve Divisor Process では、整数除算を整数乗算とシフト演算で近似するためのパラメータを計算します。
除算は他の演算に比べて（特にハードウェア実装では）コストが高く、乗算とシフトで近似することは回路規模や処理速度を上げるために非常に重要です。

----

#### 7.10.2.6. Resolve Divisor Process

> The input for this process is a variable d.
> 
> The outputs for this process are variables divShift and divFactor that can be used to perform an approximate division by d via multiplying by divFactor and shifting right by divShift.

この処理の入力は d です。
この処理の出力は、divShift と divFactor で、dでの除算を divFactor の乗算と divShift のシフトで近似となるような値です。

> The variable n (representing the location of the most signficant bit in Abs(d) ) is set equal to FloorLog2( Abs(d) ).
> The variable e is set equal to Abs( d ) - ( 1 << n ).
> The variable f is set as follows:
>
> * If n > DIV_LUT_BITS, f is set equal to Round2( e, n - DIV_LUT_BITS ).
> * Otherwise, f is set equal to e << ( DIV_LUT_BITS - n ).

n = FloorLog2(Abs(d)) （Abs(d）のMSB位置）
e = Abs( d ) - ( 1 << n )
f は以下のとおりです。

 * n > DIV_LUT_BITS ならば、f = Round2( e, n - DIV_LUT_BITS ).
 * そうでなければ、f = e << ( DIV_LUT_BITS - n ).


>The output variable divShift is set equal to ( n + DIV_LUT_PREC_BITS ).
>The output variable divFactor is set as follows:
>
> * If d is less than 0, divFactor is set equal to -Div_Lut[ f ].
> * Otherwise, divFactor is set equal to Div_Lut[ f ].

divShift = (n + DIV_LUT_PERC_BITS)
divFactor は以下のとおりです。

 * d<0 ならば、divFactor = -Div_Lut[f]
 * そうではなければ、divFactor = Div_Lut[f]

>The lookup table Div_Lut is specified as:

ルックアップテーブルは以下のとおりです。

```C++
Div_Lut[DIV_LUT_NUM] = {
  16384, 16320, 16257, 16194, 16132, 16070, 16009, 15948, 15888, 15828, 15768,
  15709, 15650, 15592, 15534, 15477, 15420, 15364, 15308, 15252, 15197, 15142,
  15087, 15033, 14980, 14926, 14873, 14821, 14769, 14717, 14665, 14614, 14564,
  14513, 14463, 14413, 14364, 14315, 14266, 14218, 14170, 14122, 14075, 14028,
  13981, 13935, 13888, 13843, 13797, 13752, 13707, 13662, 13618, 13574, 13530,
  13487, 13443, 13400, 13358, 13315, 13273, 13231, 13190, 13148, 13107, 13066,
  13026, 12985, 12945, 12906, 12866, 12827, 12788, 12749, 12710, 12672, 12633,
  12596, 12558, 12520, 12483, 12446, 12409, 12373, 12336, 12300, 12264, 12228,
  12193, 12157, 12122, 12087, 12053, 12018, 11984, 11950, 11916, 11882, 11848,
  11815, 11782, 11749, 11716, 11683, 11651, 11619, 11586, 11555, 11523, 11491,
  11460, 11429, 11398, 11367, 11336, 11305, 11275, 11245, 11215, 11185, 11155,
  11125, 11096, 11067, 11038, 11009, 10980, 10951, 10923, 10894, 10866, 10838,
  10810, 10782, 10755, 10727, 10700, 10673, 10645, 10618, 10592, 10565, 10538,
  10512, 10486, 10460, 10434, 10408, 10382, 10356, 10331, 10305, 10280, 10255,
  10230, 10205, 10180, 10156, 10131, 10107, 10082, 10058, 10034, 10010, 9986,
  9963, 9939, 9916, 9892, 9869, 9846, 9823, 9800, 9777, 9754, 9732,
  9709, 9687, 9664, 9642, 9620, 9598, 9576, 9554, 9533, 9511, 9489,
  9468, 9447, 9425, 9404, 9383, 9362, 9341, 9321, 9300, 9279, 9259,
  9239, 9218, 9198, 9178, 9158, 9138, 9118, 9098, 9079, 9059, 9039,
  9020, 9001, 8981, 8962, 8943, 8924, 8905, 8886, 8867, 8849, 8830,
  8812, 8793, 8775, 8756, 8738, 8720, 8702, 8684, 8666, 8648, 8630,
  8613, 8595, 8577, 8560, 8542, 8525, 8508, 8490, 8473, 8456, 8439,
  8422, 8405, 8389, 8372, 8355, 8339, 8322, 8306, 8289, 8273, 8257,
  8240, 8224, 8208, 8192
}
```