Papers - Accu CVu 21(5)

Code Critique Competition 59

Martin Moene < m.j.moene@eld.physics.LeidenUniv.nl >

Initially, I thought I'd talk to Roger to learn more about what the decimal to hexadecimal converter should be able to do and --no less important-- what not[1]. Maybe that's not a usual practice in this competition, maybe it's just "not done." Anyway, I didn't.

One of the things that isn't immediately clear is if the conversion should handle negative numbers and if so, in what way. What does show through the implementation though, is an interactive decimal to hexadecimal converter that does not provide additional formatting and does not handle negative numbers. Actually, it only handles a subset of N₁.

On to the code at hand. To begin with, the decimal to hexadecimal conversion fails for values where the result of the modulo 16 division (value % 16) is in the range 0..9. In the switch's default case, the value of the numbers 0..9 are used as-is, whereas they should be converted to the characters '0'..'9'. The single hexadecimal-digit conversion that enumerates values 11 to 15 can easily be replaced with a compact algorithmic approach and subsequently the whole single-figure conversion can be extracted[2] to a separate function such as:

inline char to_char( const int x )
{
   return static_cast<char>(
      x <= 9 ? '0' + x : 'A'-10 + x );
}

The function's name does not hint at the hexadecimal notation, and that's not without reason. When I use the hexadecimal notation, it often is when programming hardware registers whose bits represent operations such as select ADC number x, or clear FIFO. It can be helpful to see the value of those bits separately, that is in binary notation. It may well be that we can present the numbers in hexadecimal (base 16) as well as binary (base 2) notation with very little extra effort.

On my Palm Zire 72 I use Ding Zhaojie's Megatops BinCalc[3] . It has a nice equal opportunity[4] user interface for the binary input-output.

Presented an example how easy visual programming is, I can't help to ask: Ah, can I also grab and move the needle and read the corresponding decimal value on the knob? But I digress...

What then are the things that raise our eyebrows or that we can't resist to comment on? There are quite a few:

• omit the C header file stdio.h, this is a C++ program that uses iostreams
  
• there's also no need for  stdio.h at all in the current program
  
• variable cStack can be declared locally in function decToHex()
  
• make the conversion reusable by separating conversion and output
  
• this also makes it easier to test[5]
• showNum can be declared const
  
• variable storeNum can be defined at its first use in the while loop
• literal 16 should be replaced by a constant such as base and defined as const int base = 16
  
• prefer to declare decToHex()'s argument const int num  and
  
• define int todo = num and use it as todo /= base in the computation
• a C++-style cast should be used in the default case, not a C-style cast
  
• the /= operator can be used instead of = and / separately
  
• the conversion function accepts signed numbers but it does not handle negative numbers properly
  
• it would be useful for example to show -1 as FFFF (the number of Fs depend on sizeof(int) )
  
• it took me some time to realise that decToHex(0) is a special case of error: it generates no output at all[6]
  
• this can be corrected by replacing the while loop with a do-while loop
• the program lacks error handling

Given what we know now, I suggest to use the following adapted main function:

#include <string>       // std::string
#include <iostream>     // std::cout, cerr

int to_int( std::string text )
{
   return atoi( text.c_str() );
}

int main( int argc, char* argv[] )
{
   const int default_base = 16;

   try
   {
      const int base =
          (argc > 1) ? to_int( argv[1] )
                     : default_base;

      report( std::cout, "cout",
        read( std::cin , "cin" ), base );
   }
   catch ( std::exception const& e )
   {
      std::cerr << e.what() << std::endl;
      return EXIT_FAILURE;
   }

   return EXIT_SUCCESS;
}

Note that the program accepts the base to present the number in as the program's first argument. It also contains the try-catch skeleton to handle errors. Implementation of various other ideas to make the program 'more wonderful' are left to the reader:

• accept a list of bases to present the number in
  
• accept input also in binary, octal and hexadecimal notation
  
• provide help via a commandline option such as -h or --help
  

The supporting input-output functions  include checks on the streams and they report bad luck by throwing an exception with an informative message.

const std::string progname = "decToBase";

int read( std::istream& is, std::string name )
{
   int integer = 0;
   is >> integer;

   if ( !is )
   {
      throw std::runtime_error(
         progname +
         ": cannot read number from stream '" +
         name + "'" );
   }

   return integer;
}

void report( std::ostream& os, std::string name,
                    const int x, const int base )
{
   os <<
      x <<" in base '" << base << "' "
      "is '" << to_string( x, base ) << "'"  <<
      std::endl;

   if ( !os )
   {
      throw std::runtime_error(
         progname +
         ": cannot not write to stream '" +
         name + "'" );
   }
}

 The new prototype of the conversion function is:

std::string to_string( const int x,
                       const int base );

What I like about the converter's original implementation is its use of std::stack, well actually I like its use of a container from the C++ standard library. In the following implementation, I've continued this approach.

std::string to_string( const int x,
                       const int base = 10 )
{
   REQUIRE( base >= 2);
   REQUIRE( base <= 36 );

   unsigned int ux( x );
   unsigned int ubase( base );

   std::string result;

   do
   {
      result.insert(
         0, // position
         1, // count
         to_char( ux % ubase )
      );
   }
   while( ( ux /= ubase ) > 0 );

   return result;
}

Indeed, std::string is a container, be it a rather awkward one. Kevlin Henney wrote several interesting articles on the container aspect of std::string[7]. He also argues that using high-level (generic) programming constructs are part of a modern approach to teaching C++[8].

A simple yet effective signed-to-unsigned transformation enables us to present negative numbers. Represented unsigned, an originally negative number can be treated as its corresponding bit pattern. To prevent signed-unsigned mismatch in the computations, these also use base as an unsigned number[9]. To make the signed-unsigned transformation more explicit than it is now, a static_cast<unsigned int>() can be used.

Using the requested number-base in two computations is all that's needed to present the converted number in base 2 with a highest figure of '1' up to and including base 36 with a highest figure of 'Z'. Zero will convert properly now, with the while loop replaced by a do-while loop with the extracted to_char()  function. The loop still collects the figures from least to most significant and puts them one by one at the front of the string as they're computed.

In the original while loop the test and the advance operations are rather far apart. Contrast this with the do-while loop that combines them into a single expression. I would have used a for loop hadn't the loop required to be executed at least once. However I slightly prefer the do-while over the following for loop that contains zero as a special-case.

std::string result( 0 == ux ? "0" : "" );

for( ; ux > 0; ux /= base )
{
   result.insert(
      0, // position
      1, // count
      to_char( ux % base )
   );
}

And here are the results:

prompt>decToBase.exe
123
123 in base '16' is '7B'
prompt>decToBase.exe 2
123
123 in base '2' is '1111011'
prompt>decToBase.exe
-1
-1 in base '16' is 'FFFFFFFF'

Initially, before I revisited std::string and found a usable insert method, I worked out another solution that I like to share.

#include <iterator>     // std::inserter
#include <vector>       // std::vector<>
#include <string>       // std::string

template< typename range, typename output >
output rcopy( range const& source, output sink )
{
   return std::copy(
      source.rbegin(), source.rend(), sink );
}

std::string to_string( const int x, const int base = 10 )
{
   REQUIRE( base >= 2 );
   REQUIRE( base <= 36 );

   unsigned int ux( x );
   unsigned int ubase( base );

   std::vector<char> reversed;

   do
   {
      reversed.push_back( to_char( ux % ubase ) );
   }
   while( ( ux /= ubase ) > 0 );

   std::string result;
   rcopy( reversed, std::back_inserter( result ) );

   return result;
}

The std::stack container is replaced with the more general std::vector. As a result, the std::copy algorithm can be used to insert the collected figures in a std::string in reverse order, by employing reverse iterators on the vector named reversed. The idea to condense the copy operation as shown is taken from Software As Read, by Jon Jagger[10].

Other solutions spring to mind, for example using a string stream.

#include <iomanip>      // std::hex
#include <sstream>      // std::stringstream

std::string to_hex( const int x )
{
   std::stringstream oss;

   oss << std::hex << x;

   return oss.str();
}

Yet another uses the C function _ltoa().

std::string to_string( const int x, const int base )
{
   REQUIRE( base >= 2 );
   REQUIRE( base <= 36 );

   char buf[ 8 * sizeof( x ) + 1 ];

   return _ltoa( x, buf, base );
}

What are your expectations? Recall the exception handling in main() and imagine you enter a base on the commandline that is outside the valid range of 2-36 and request a conversion. The conversion function receives a base that it cannot handle in a constructive way. This is a situation that should not happen and thus it is a programming error[11].  Here is macro REQUIRE's job: throw an exception if the stated requirements, or preconditions[12] base >= 2 and base <= 36 are not true, as it occurs in[13]:

prompt>decToBase.exe 1
123
decToBase.cpp(60): expected 'base >= 2'

Note that a user entering an invalid base in fact represents an environmental error, that is, an error that is not unexpected to happen. It is the program that should prevent the invalid base to reach the conversion function that is known to be unable to handle it[14]. Contrast this with a programming error that leads to the same situation: that is not expected to happen.

Macro REQUIRE is defined as follows.

#include <stdexcept>    // std::runtime_exception

#define REQUIRE( expr ) \
   if ( !(expr) ) \
   { \
      throw std::runtime_error( \
         to_string(__FILE__) + \
         "(" + to_string(__LINE__) + \
         "): expected '" + #expr + "'" ); \
   }

Macro REQUIRE uses two conversion shims[15], one of which is the already familiar number-to-string converter. The story recurses.

std::string to_string( std::string text )
{
   return text;
}

std::string to_string( const int x
                   /*, const int base = 10 */ )
{
   // guess what
}

The choice of the parameter type of the first to_string() may come as a surprise. However, with std::string as its parameter type, the function can also be used with arguments that are convertible to that type, such as __FILE__'s type char*.

What's left of the original program? One line: there where one comes to provide his or her input:

std::cin >> integer;

Especially in this context I like the word integer.


Notes and References

[1]  Don Wells. The Customer is Always Available, http://www.extremeprogramming.org/rules/customer.html
[2] Martin Fowler. Refactoring: Improving the Design of Existing Code, http://martinfowler.com/books.html#refactoring
[3] Ding Zhaojie. Megatops BinCalc 1.0.3 (for PC and Palm), http://bincalc.googlepages.com/
[4] Leogo: An Equal Opportunity User Interface for Programming, section 2.1 Equal Opportunity Interfaces, http://www.cosc.canterbury.ac.nz/andrew.cockburn/papers/jour_leo.pdf
[5] Kevlin Henney. Put to the test, http://www.curbralan.com/papers/PutToTheTest.pdf
[6] Indeed, I should have created a unit test right at the start.
[7a] Kevlin Henney. Stringing Things Along, http://www.curbralan.com/papers/StringingThingsAlong.pdf
[7b] Kevlin Henney. Highly Strung, http://www.curbralan.com/papers/HighlyStrung.pdf
[7c] Kevlin Henney. The Next Best String, http://www.curbralan.com/papers/TheNextBestString.pdf
[8] Kevlin Henney. The miseducation of C++, http://www.two-sdg.demon.co.uk/curbralan/papers/TheMiseducationOfC++.pdf
[9] Prefer to reserve unsigned types for types that represent bit patterns or flags; to reduce occurrences of signed-unsigned mismatch, prefer signed types for numbers even if these numbers are non-negative only. See Google C++ Style Guide, Integer Types, http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Integer_Types
[10] Jon Jagger. Software As Read, http://www.jaggersoft.com/pubs/SoftwareAsRead.htm
[11] Eiffel Software. Building bug-free O-O software: An Introduction to Design by Contract™, http://www.eiffel.com/developers/design_by_contract_in_detail.html
[12] A precondition violation is an unexpected error for the implementor, but not for the user. A postcondition violation is an unexpected error for the user if the precondition was valid on entry, but not for the implementor.
[13] I used literals in the precondition test, so they show up as 2 and 36 in the error message, not as BASE_MIN and BASE_MAX.
[14] To illustrate the precondition violation, I omitted base = checked_base(...) from main().
[15] M. D. Wilson. "Shims – A Definition", http://www.synesis.com.au/resources/articles/cpp/shims.pdf

---

Original Listing:

home   sitemap   contact   copyrights
Page last changed fourteen years ago

Martin Moene Electronics Department · Leiden Institute of Physics · Leiden University