Provide (non Gay) dtoa for fixed notation.

Provide (non Gay) dtoa for fixed notation.

Committed: http://code.google.com/p/v8/source/detail?r=4591

[William Hesse, 2010-05-04 07:33:13]

All reviewed except fixed-dtoa.cc.  Still working on that one.

http://codereview.chromium.org/1865001/diff/1/5002
File src/dtoa.cc (right):

http://codereview.chromium.org/1865001/diff/1/5002#newcode68
src/dtoa.cc:68: if (FastDtoa(v, buffer, length, point)) return true;
What does FastDtoa return if not "true"?  If you don't use this value, why not
return true, for parallelism with FastFixedDtoa?

http://codereview.chromium.org/1865001/diff/1/13001
File src/dtoa.h (right):

http://codereview.chromium.org/1865001/diff/1/13001#newcode37
src/dtoa.h:37: // Fixed number of digits after the comma.
after the radix point (or decimal point).  To me, commas are what go between
every three digits.

http://codereview.chromium.org/1865001/diff/1/13001#newcode62
src/dtoa.h:62: //   'requested_digits' digits after the comma. The produced
digits might be too
decimal point

http://codereview.chromium.org/1865001/diff/1/13001#newcode69
src/dtoa.h:69: //   any other digit would not satisfy the internal identity
requirement.
I would say "The returned buffer may contain digits that would be truncated from
the shortest representation of the input."

http://codereview.chromium.org/1865001/diff/1/13001#newcode72
src/dtoa.h:72: //   'requested_digits', the function is allowed to return less
digits, in which
fewer digits

http://codereview.chromium.org/1865001/diff/1/19001
File src/fast-dtoa.h (right):

http://codereview.chromium.org/1865001/diff/1/19001#newcode39
src/fast-dtoa.h:39: // v must be strictly greater than 0 and it must not be
Infinity or NaN.
A strictly positive finite double?

http://codereview.chromium.org/1865001/diff/1/21001
File src/fixed-dtoa.h (right):

http://codereview.chromium.org/1865001/diff/1/21001#newcode35
src/fixed-dtoa.h:35: // 'fractional_count' digits after the comma.
radix point, decimal point, radix marker?
You are not even typing a comma in your examples - you are typing a period
("0.001").

http://codereview.chromium.org/1865001/diff/1/21001#newcode43
src/fixed-dtoa.h:43: // Note: the length of the returned buffer has no meaning
wrt the significance
Same change to wording as suggested earlier.

http://codereview.chromium.org/1865001/diff/1/3001
File test/cctest/gay-fixed.h (right):

http://codereview.chromium.org/1865001/diff/1/3001#newcode35
test/cctest/gay-fixed.h:35: double v;
Are these just precomputed values?  What do they have to do with the Gay
algorithm, except that it was used to compute them?  Why not "PrecomputedFixed"?

http://codereview.chromium.org/1865001/diff/1/5001
File test/cctest/test-fixed-dtoa.cc (right):

http://codereview.chromium.org/1865001/diff/1/5001#newcode77
test/cctest/test-fixed-dtoa.cc:77:
CHECK(FastFixedDtoa(6.9999999999999989514240000e+21, 5, buffer, &length,
&point));
Line too long?

[Florian Loitsch, 2010-05-04 08:51:30]

http://codereview.chromium.org/1865001/diff/1/5002
File src/dtoa.cc (right):

http://codereview.chromium.org/1865001/diff/1/5002#newcode68
src/dtoa.cc:68: if (FastDtoa(v, buffer, length, point)) return true;
On 2010/05/04 07:33:13, William Hesse wrote:
> What does FastDtoa return if not "true"?  If you don't use this value, why not
> return true, for parallelism with FastFixedDtoa?
This is already in preparation for a future patch. But for now make it parallel
with FastFixedDtoa.

http://codereview.chromium.org/1865001/diff/1/13001
File src/dtoa.h (right):

http://codereview.chromium.org/1865001/diff/1/13001#newcode37
src/dtoa.h:37: // Fixed number of digits after the comma.
On 2010/05/04 07:33:13, William Hesse wrote:
> after the radix point (or decimal point).  To me, commas are what go between
> every three digits.

Done.

http://codereview.chromium.org/1865001/diff/1/13001#newcode62
src/dtoa.h:62: //   'requested_digits' digits after the comma. The produced
digits might be too
On 2010/05/04 07:33:13, William Hesse wrote:
> decimal point

Done.

http://codereview.chromium.org/1865001/diff/1/13001#newcode69
src/dtoa.h:69: //   any other digit would not satisfy the internal identity
requirement.
On 2010/05/04 07:33:13, William Hesse wrote:
> I would say "The returned buffer may contain digits that would be truncated
from
> the shortest representation of the input."

Done.

http://codereview.chromium.org/1865001/diff/1/13001#newcode72
src/dtoa.h:72: //   'requested_digits', the function is allowed to return less
digits, in which
On 2010/05/04 07:33:13, William Hesse wrote:
> fewer digits

Done.

http://codereview.chromium.org/1865001/diff/1/19001
File src/fast-dtoa.h (right):

http://codereview.chromium.org/1865001/diff/1/19001#newcode39
src/fast-dtoa.h:39: // v must be strictly greater than 0 and it must not be
Infinity or NaN.
On 2010/05/04 07:33:13, William Hesse wrote:
> A strictly positive finite double?
thanks.
done.

http://codereview.chromium.org/1865001/diff/1/21001
File src/fixed-dtoa.h (right):

http://codereview.chromium.org/1865001/diff/1/21001#newcode35
src/fixed-dtoa.h:35: // 'fractional_count' digits after the comma.
On 2010/05/04 07:33:13, William Hesse wrote:
> radix point, decimal point, radix marker?
> You are not even typing a comma in your examples - you are typing a period
> ("0.001").

Done.

http://codereview.chromium.org/1865001/diff/1/21001#newcode43
src/fixed-dtoa.h:43: // Note: the length of the returned buffer has no meaning
wrt the significance
On 2010/05/04 07:33:13, William Hesse wrote:
> Same change to wording as suggested earlier.

Done.

http://codereview.chromium.org/1865001/diff/1/3001
File test/cctest/gay-fixed.h (right):

http://codereview.chromium.org/1865001/diff/1/3001#newcode35
test/cctest/gay-fixed.h:35: double v;
On 2010/05/04 07:33:13, William Hesse wrote:
> Are these just precomputed values?  What do they have to do with the Gay
> algorithm, except that it was used to compute them?  Why not
"PrecomputedFixed"?

Done.

http://codereview.chromium.org/1865001/diff/1/5001
File test/cctest/test-fixed-dtoa.cc (right):

http://codereview.chromium.org/1865001/diff/1/5001#newcode77
test/cctest/test-fixed-dtoa.cc:77:
CHECK(FastFixedDtoa(6.9999999999999989514240000e+21, 5, buffer, &length,
&point));
On 2010/05/04 07:33:13, William Hesse wrote:
> Line too long?

Done.

[William Hesse, 2010-05-04 09:43:46]

Reviewed fixed-dtoa.cc to line 235.  Almost done.

http://codereview.chromium.org/1865001/diff/1/17001
File src/fixed-dtoa.cc (right):

http://codereview.chromium.org/1865001/diff/1/17001#newcode45
src/fixed-dtoa.cc:45: void Multiply(uint32_t by) {
I think "by" is a bad name.  How about:
short_factor
short_multiplicand
multiplicand
r
r32
factor32

http://codereview.chromium.org/1865001/diff/1/17001#newcode63
src/fixed-dtoa.cc:63: ASSERT(-64 <= by && by <= 64);
shift_amount

http://codereview.chromium.org/1865001/diff/1/17001#newcode84
src/fixed-dtoa.cc:84: // The returned value equals this / 2^position
The standard name for this is DivMod, I think.  Maybe DivModPowerof2?

I would say: Modifies *this to *this MOD (2 ^ position), returns *this DIV (2 ^
position).  Or use (1 << position) instead of 2 ^ position.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode8
src/fixed-dtoa.cc:8: //     * Redistributions in binary form must reproduce the
above
The code review tool is showing lint errors on many of the files.  These should
be stamped out.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode133
src/fixed-dtoa.cc:133: static void FillDigits32(uint32_t number, Vector<char>
buffer, int* length) {
A comment or an assert that buffer length is > 9 or 10?

http://codereview.chromium.org/1865001/diff/36001/51001#newcode143
src/fixed-dtoa.cc:143: for (int i = 0, j = number_length - 1; i < j; ++i, --j) {
If you go to the trouble of making two variables for efficiency, why not make
them pointer variables, since all the uses are of the same form?  Can you check
left < right with two pointers in the same array?  Yes: If two pointers point to
elements of the same array or to the element one beyond the end of the array,
the pointer to the object with the higher subscript compares higher. Comparison
of pointers is guaranteed valid only when the pointers refer to objects in the
same array or to the location one past the end of the array.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode143
src/fixed-dtoa.cc:143: for (int i = 0, j = number_length - 1; i < j; ++i, --j) {
char* i = buffer + *length, *j = i + number_length - 1; i < j; ++i, --j

http://codereview.chromium.org/1865001/diff/36001/51001#newcode205
src/fixed-dtoa.cc:205: buffer[0] = '1';
This needs a comment.  It is only because carries started in the units place
that we know all the digits have changed to '0', so that adding an implicit 0 on
the right is the same as inserting '10' on the left.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode214
src/fixed-dtoa.cc:214: ASSERT(exponent <= 0);
Comment: fractionals is a fixed-point number, with binary point at bit
(-exponent).  Inside the function, the non-converted remainder of fractionals is
a fixed point number, with binary point at bit point.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode217
src/fixed-dtoa.cc:217: ASSERT(fractionals >> 56 == 0);
Isn't (fractionals >> -exponent == 0) also a precondition?

http://codereview.chromium.org/1865001/diff/36001/51001#newcode218
src/fixed-dtoa.cc:218: int point = 0;
Is there a reason to separate the declaration and initialization of point?

http://codereview.chromium.org/1865001/diff/36001/51001#newcode224
src/fixed-dtoa.cc:224: fractionals *= 5;
The fact that this multiplication doesn't overflow is subtle.  Based on the fact
that if exponent is 64, then by the time that fractionals (which starts less
that 1 << 56) gets to be 61 bits long, then point is 62, and 61 ofter the
decrement.  Should be commented.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode230
src/fixed-dtoa.cc:230: fractionals &= point_mask;
Couldn't point_mask be replaced by 
fractionals -= static_cast<uint64_t>(digit) << point; ?

[William Hesse, 2010-05-04 10:43:15]

http://codereview.chromium.org/1865001/diff/36001/51001
File src/fixed-dtoa.cc (right):

http://codereview.chromium.org/1865001/diff/36001/51001#newcode244
src/fixed-dtoa.cc:244: // point loccation.
location.

Again, comment that point is decremented by 3 before we get numbers above 1.0 in
fixed point notation, so that we don't overflow.  Why not multiply by 5^8, so
that you get an int32 worth of integer digits to convert at a time?

http://codereview.chromium.org/1865001/diff/36001/51001#newcode286
src/fixed-dtoa.cc:286: if (exponent > 20) return false;
Isn't exponent a binary exponent?  I thought 20 was a limit on the decimal
exponent.  Why do we need this (rather low) limit on the binary exponent?

[Florian Loitsch, 2010-05-04 12:32:51]

http://codereview.chromium.org/1865001/diff/1/17001
File src/fixed-dtoa.cc (right):

http://codereview.chromium.org/1865001/diff/1/17001#newcode45
src/fixed-dtoa.cc:45: void Multiply(uint32_t by) {
On 2010/05/04 09:43:46, William Hesse wrote:
> I think "by" is a bad name.  How about:
> short_factor
> short_multiplicand
> multiplicand
> r
> r32
> factor32
> 

Done.

http://codereview.chromium.org/1865001/diff/1/17001#newcode63
src/fixed-dtoa.cc:63: ASSERT(-64 <= by && by <= 64);
On 2010/05/04 09:43:46, William Hesse wrote:
> shift_amount

Done.

http://codereview.chromium.org/1865001/diff/1/17001#newcode84
src/fixed-dtoa.cc:84: // The returned value equals this / 2^position
On 2010/05/04 09:43:46, William Hesse wrote:
> The standard name for this is DivMod, I think.  Maybe DivModPowerof2?
> 
> I would say: Modifies *this to *this MOD (2 ^ position), returns *this DIV (2
^
> position).  Or use (1 << position) instead of 2 ^ position.

Done.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode8
src/fixed-dtoa.cc:8: //     * Redistributions in binary form must reproduce the
above
On 2010/05/04 09:43:46, William Hesse wrote:
> The code review tool is showing lint errors on many of the files.  These
should
> be stamped out.
Many of them are incorrect (for instance we don't have directories for sources).

http://codereview.chromium.org/1865001/diff/36001/51001#newcode133
src/fixed-dtoa.cc:133: static void FillDigits32(uint32_t number, Vector<char>
buffer, int* length) {
On 2010/05/04 09:43:46, William Hesse wrote:
> A comment or an assert that buffer length is > 9 or 10?
I added a comment in fixed-dtoa.h that requires the buffer to be big enough to
hold the result. We continuously check out-of-bounds due to the use of a Vector.
I don't see why another assert/comment would help here.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode143
src/fixed-dtoa.cc:143: for (int i = 0, j = number_length - 1; i < j; ++i, --j) {
On 2010/05/04 09:43:46, William Hesse wrote:
> If you go to the trouble of making two variables for efficiency, why not make
> them pointer variables, since all the uses are of the same form?  Can you
check
> left < right with two pointers in the same array?  Yes: If two pointers point
to
> elements of the same array or to the element one beyond the end of the array,
> the pointer to the object with the higher subscript compares higher.
Comparison
> of pointers is guaranteed valid only when the pointers refer to objects in the
> same array or to the location one past the end of the array.
Two variables is not for efficiency, but I found it easier to read. If you
disagree I would be willing to change.
Pointer variables are usually slower than accesses using indices (at least in
optimized code).

http://codereview.chromium.org/1865001/diff/36001/51001#newcode205
src/fixed-dtoa.cc:205: buffer[0] = '1';
On 2010/05/04 09:43:46, William Hesse wrote:
> This needs a comment.  It is only because carries started in the units place
> that we know all the digits have changed to '0', so that adding an implicit 0
on
> the right is the same as inserting '10' on the left.

Done.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode214
src/fixed-dtoa.cc:214: ASSERT(exponent <= 0);
On 2010/05/04 09:43:46, William Hesse wrote:
> Comment: fractionals is a fixed-point number, with binary point at bit
> (-exponent).  Inside the function, the non-converted remainder of fractionals
is
> a fixed point number, with binary point at bit point.

Done.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode217
src/fixed-dtoa.cc:217: ASSERT(fractionals >> 56 == 0);
On 2010/05/04 09:43:46, William Hesse wrote:
> Isn't (fractionals >> -exponent == 0) also a precondition?

Done.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode218
src/fixed-dtoa.cc:218: int point = 0;
On 2010/05/04 09:43:46, William Hesse wrote:
> Is there a reason to separate the declaration and initialization of point?

Done.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode224
src/fixed-dtoa.cc:224: fractionals *= 5;
On 2010/05/04 09:43:46, William Hesse wrote:
> The fact that this multiplication doesn't overflow is subtle.  Based on the
fact
> that if exponent is 64, then by the time that fractionals (which starts less
> that 1 << 56) gets to be 61 bits long, then point is 62, and 61 ofter the
> decrement.  Should be commented.

Done.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode230
src/fixed-dtoa.cc:230: fractionals &= point_mask;
On 2010/05/04 09:43:46, William Hesse wrote:
> Couldn't point_mask be replaced by 
> fractionals -= static_cast<uint64_t>(digit) << point; ?
> 
much better. thanks.
Done.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode244
src/fixed-dtoa.cc:244: // point loccation.
On 2010/05/04 10:43:15, William Hesse wrote:
> location.
> 
> Again, comment that point is decremented by 3 before we get numbers above 1.0
in
> fixed point notation, so that we don't overflow.
done
>  Why not multiply by 5^8, so
> that you get an int32 worth of integer digits to convert at a time?

I'm not sure it will buy us much. Especially on ARM where there exists no
division operation.

http://codereview.chromium.org/1865001/diff/36001/51001#newcode286
src/fixed-dtoa.cc:286: if (exponent > 20) return false;
On 2010/05/04 10:43:15, William Hesse wrote:
> Isn't exponent a binary exponent?  I thought 20 was a limit on the decimal
> exponent.  Why do we need this (rather low) limit on the binary exponent?
added comment.

[William Hesse, 2010-05-05 08:37:28]

LGTM.  I don't think the indexed code with two variables is as optimal, because
there is also an addition to the index inside the expressions.  If the compiler
knew that *length was constant, it could optimize buffer[*length + j] to
a memory operand, but I doubt it does.  We know *length is constant during the
loop, so we can do it.