ANN: Optimized numeric_cast<> implementation

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2001-10-25 15:50:00

Hi boosters,

Those of you who have followed the development of the boost template based
math library (thread with "Math functions" in the subject) will know that it
was pointed out that there are optimization issues with numeric_cast<> that
prevent it from being used as broadly as we need.

Based on my prior work on numerical conversion functions, I submit here a
new optimized implementation of numeric_cast<>.

Motivation:
~~~~~~~~

The current numeric_cast<> implementation presents the following drawbacks
(or at least this is what I could infer from the code):
* It doesn't has a return type optimization for the trivial case
Target==Source.
* It performs the same runtime range-checking logic, even in cases when
range checking is unnecessary: for example, when Target=double and
Source=float.
* It can not be used -or it is not clear how would it behave- with mixed
integral/float combinations.

The new implementation and the new additional interface.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The interface to numeric_cast<> itself remains the same (except for the
optimizations introduced).
But in this new implementation, numeric_cast is a wrapper around some new
tools which I describe below:

(A) boost::numeric_range<N>

This new class formalizes a solution to the "problem" with
std::numeric_limits::min().
It exposes the following interface which is consistent across integer and
floating point types:

boost::numeric_range<N>::lowest() // closer to -INF
boost::numeric_range<N>::highest() // closer to +INF
boost::numeric_range<N>::smallest() // closer to 0

(B) boost::numeric_cast_traits<T,S>

This new class is the core of the submission.
It is a traits class that provides information and optimized methods for the
conversion from values of type S to values of type T.

The following is a transcription of the documentation included in its header
file:

//
// numeric_cast_traits<T,S> traits.
//
// This traits class provides facilities for the conversion
//   from a value 's' of type 'S'
//   to   a value 't' of type 'T'.
//
// The facilities are:
//
//   static const int  numeric_cast_traits<T,S>::mixture
//   static const int  numeric_cast_traits<T,S>::sign_mixture
//   static const bool numeric_cast_traits<T,S>::subranged
//   static const bool numeric_cast_traits<T,S>::trivial
//   type              numeric_cast_traits<T,S>::super_type
//   type              numeric_cast_traits<T,S>::sub_type
//   type              numeric_cast_traits<T,S>::arg_type
//   type              numeric_cast_traits<T,S>::ret_type
//   struct            numeric_cast_traits<T,S>::range_checker
//   struct            numeric_cast_traits<T,S>::converter
//
// mixture
//
//   This integral constant expression of type int determines
//   one of the four integral/float possible combinations.
//   It takes one of the following values:
//
//     numeric_cast_mixture::integral_to_integral
//     numeric_cast_mixture::integral_to_float
//     numeric_cast_mixture::float_to_integral
//     numeric_cast_mixture::float_to_float
//
// sign_mixture
//
//   This integral constant expression of type int,
//   determines one of the four signed/unsigned
//   possible combinations.
//   It takes one of the following values:
//
//     numeric_cast_sign_mixture::unsigned_to_unsigned
//     numeric_cast_sign_mixture::signed_to_signed
//     numeric_cast_sign_mixture::signed_to_unsigned
//     numeric_cast_sign_mixture::unsigned_to_signed
//
// subranged
//
//   This integral constant expression of type bool
//   conceptually determines if the target T is "subranged"
//   with respect to the source type S.
//   A value of true implies that the converted value might be
//   truncated or rounded off, because the target type T cannot
//   represent every value of the source type S.
//   A value of false implies that the conversion
//   will always be exact regardless the actual source value 's',
//   because the type T can represent every value of type S.
//   Notice that this is a compile-time predicate,
//   independent of any actual value of type S to be converted.
//
// trivial
//
//   This integral constant expression of type bool
//   is 'true' if both source and target types are the same, that is
//   if T==S.
//   It is false otherwise.
//
// super_type
//
//   This is the type to which two operands of types S and T
//   must be promoted in order to participate in a common arithmetic
//   or relational operation.
//   It is either T or S, depending on the value of subranged.
//
// sub_type
//
//   This is the type T or S which is not the super_type.
//
// arg_type
//
//   This type is either 'S' or 'S const&'.
//   It represents the 'optimal' argument type for the functions
//   in range_checker and converter.
//
//   If S is a built-in type, arg_type is 'S', otherwise, it is
//   'S const&'.
//
// ret_type
//
//   This type is either 'T' or 'T const&'
//   It represents the return type of the member function
//
//     converter::cvt
//
//    If T==S, ret_type is 'T const&' otherwise, it is 'T'.
//
// range_checker
//
//   This object is used to perform range checking for the conversion
//   from a particular value 's' to the type T.
//   A range_checker object exposes the following interface:
//
//     static int out_of_range ( arg_type s ) ;
//
//       This static member function determines if the value 's'
//       can be represented by the type T without truncation.
//       It does not determine if the conversion is exact; that is,
//       a rounding (inexact) conversion is considered to be in range.
//       For instance, a conversion producing a floating point
//       underflow is considered in range.
//
//       The test is conceptually the same as
//
//             s >= numeric_range<T>::lowest ()
//          && s <= numeric_range<T>::highest()
//
//       The return value is one the the following constants:
//
//         range_check_result::cInRange
//         range_check_result::cNegOverflow
//         range_check_result::cPosOverflow
//
//     static void assert_in_range ( arg_type s ) ;
//
//         this static member function calls result=out_of_range(s),
//         and if result!=cInRange, throws a corresponding exception:
//
//           result==cNegOverflow -> throw boost::negative_overflow();
//           result==cPosOverflow -> throw boost::positive_overflow();
//
// converter
//
//   This object is used to perform a conversion
//   from s of type S to t of type T.
//
//   A converter object exposes the following interface:
//
//     static ret_type cvt ( arg_type s ) ;
//
//  This object uses internally range_checker::assert_in_range(), thus,
//  it might throw any of the exceptions thrown by the check.
//
// NOTE: both range_checker and converter are optimized according to
//       combined properties of T and S.

the core of the optimizations resides in the different range_checker and
converters statically selected
according to S and T.

As you can see in the header "numeric_cast_traits_detail.hpp", there are 4
range checkers and
3 converters.

NOTE: the classes below are implementation details, I shown them here so you
can get an idea of how the optimizations work.

full_range_checker::assert_in_range(s)
    asserts that ( s >= lowest(T) && s <= highest(T))

void_range_checker::assert_in_range(s)
    does effectively nothing.
    it is selected when the conversion is trivial or not subranged.

non_negative_range_checker::assert_in_range(s)
    asserts that ( s>= 0 )
    it is used when there is a signed to unsigned conversion and the target
type has bigger positive range.

positive_range_checker::assert_in_range(s)
    asserts that ( s < highest(T))
    it is used when there is an unsigned to signed conversion. (the negative
range is implicitly OK)

non_rounding_converter::cvt
    converts from a floating point or integer type to another floating point
type.

rounding_converter::cvt
    converts from a floating point type to an integer type.

void_converter::cvt
    effectively does nothing: returns a const reference to its const
reference argument.
    it is used when T==S.

If you look closely you will discover some "gaps".
In order to fill those gaps I need further definitions and choices that I
can't make myself.

a) The rounding from floating point to integer is fixed.
    I couldn't figured out how to let the user plug in a rounding scheme
without too much interface clutter.
    I think it will end up using *one* of the new C99 rounding functions
when they become available

b) There isn't control for inexact conversions, such as underflow.
c) out_of_range conditions throw exceptions. On some applications it might
be better to return the truncated value instead.

The overall design contemplates the above gaps, so it would be relatively
easy to change the code to accommodate things.

the code:
~~~~~~

I uploaded the code in a new folder on the Files Section:

  http://groups.yahoo.com/group/boost/files/improved_numeric_cast/

The code is split in several files. They are intended to be in different
directories of a boost installation:

boost\
    numeric_cast.hpp
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
.hpp
    numeric_cast_traits.hpp
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
_traits.hpp
    numeric_range.hpp
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_rang
e.hpp
    detail\
        numeric_cast_traits_detail.hpp
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
_traits_detail.hpp
        numeric_cast_range_detail.hpp
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
_range_detail.hpp
        meta_programing_tools.hpp
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/meta_program
ing_tools.hpp
    libs\
        numeric_cast_test.cpp
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
_test.cpp
        numeric_cast_test_output.txt
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
_test_output.txt

There is a ZIP file with everything too:
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
.zip

The implementation:
~~~~~~~~~~~~~~~

All the files contain extensive documentation; however, the "detail" headers
are rather complex.
I tried my best at making the implementation as readable as possible, but
also as portable as possible, so most of the code looks uglier that you
would have expected, because I needed to accommodate the poor non-type
template parameter support of Borland C++ and the poor
partial-specialization support of Visual C++.

The file 'meta_programing_tools.hpp' is an update of the file
'meta_tools.hpp' that I've uploaded for my optional<> class before. It
borrowed some stuff from 'ice.hpp' and 'select_type.hpp', but for type
parameters instead of non-type parameters.

I used some of the type_traits headers.

Opinions?

Best regards,

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com