just_enough

30/06/2020

The C99 <stdint.h> header provides a plethora of type definition for platform-independent safe code: int_fast16_t, for example, provides an integer that plays well with the machine but has at least 16 bits. The int_fastxx_t and int_leastxx_t defines doesn’t guarantee a tight fit, they provide an machine-efficient fit. They find the fastest type of integer for that machine that respects the constraint.

But let’s take the problem the other way around: what about defines that gives you the smallest integer, not for the number of bits (because that’s trivial with intxx_t) but from the maximum value you need to represent?

Read the rest of this entry »


Of small copies and templates.

23/07/2019

Sometimes, it’s the little things that make a big difference. For example, moving small, not machine-sized, pieces of data may be a problem. If it happens to be machine-sized (that is, the size of something like uint32_t), then the copy is readily done by a single (integer) copy. But what if it’s, say, 5 bytes?

The first solution that comes to mind is either a for-loop or a call to a library function like memcpy. The for-loop would give something like:

char * dest = ...
char * src = ...
for (std::size_t i=0;i<5;i++) dest[i]=src[i];

If you’re lucky, the compiler understands the small copy and optimizes. More likely, it will merely unroll the loop and generate something like:

14d4:   0f b6 07    movzx  eax,BYTE PTR [rdi]
14df:   88 04 24    mov    BYTE PTR [rsp],al
14e2:   0f b6 47 01 movzx  eax,BYTE PTR [rdi+0x1]
14e6:   88 44 24 01 mov    BYTE PTR [rsp+0x1],al
14ea:   0f b6 47 02 movzx  eax,BYTE PTR [rdi+0x2]
14ee:   88 44 24 02 mov    BYTE PTR [rsp+0x2],al
14f2:   0f b6 47 03 movzx  eax,BYTE PTR [rdi+0x3]
14f6:   88 44 24 03 mov    BYTE PTR [rsp+0x3],al
14fa:   0f b6 47 04 movzx  eax,BYTE PTR [rdi+0x4]
14fe:   88 44 24 04 mov    BYTE PTR [rsp+0x4],al

Let’s see how we can fix that!

Read the rest of this entry »


Just Larger

31/10/2017

This week, something short & sweet & probably useful for generic programming: find the next integral type just bigger than a given type. The obvious application would be that if you want to add ints, you’ll want the variable that holds the sums to be larger than int. In generic programming, however, you don’t necessarily know beforehand that the base type will be int.

Turns out, while there’s’nt anything built-in to do that, it isn’t very complicated either. First, we will define a series of templates with overloads; second, we will use using to extract the type seamlessly.

We will define a struct (rather than a class, merely to avoid adding public:) that defines a type type depending on its template argument. The trick is that if T is xyz then define nested type zyx and make it public. Since we can’t (or at least, I haven’t figured how to) have some kind of switch/case on types, we will have to define explicit specializations, one for each supported (integral) type.

The simplest possible implementation would be something like this:

////////////////////////////////////////
template <typename T> struct just_larger_; // incomplete type is default

// some are implementation-specific (char may or may not be signed)
template <> struct just_larger_<char> { using type = int16_t; };

// some standard types
template <> struct just_larger_<int16_t>  { using type = int32_t;  };
template <> struct just_larger_<uint8_t>  { using type = uint16_t; };
template <> struct just_larger_<uint16_t> { using type = uint32_t; };

// "extracts" type
template <typename T>
 using just_larger=
  typename just_larger_<T>::type;

Of course, one would have to define all overloads for the basic types, the types from headers <cstddef>, <cstdint>, and any other platform- or implementation-specific headers.

The usefulness of just_larger<T> is within another template. If one of the arguments of the this template is used with just_larger, then it’s simple. If, for some reason, you do not have directly access to the type, but only to, say, a field name, you may need to use decltype, a C++11 addition. decltype gives the declared type of an entity or of an arbitrary expression.

An example of use:

#include <iostream>
#include <cstdint>
#include <typeinfo>
#include <type_traits> // for typeid and type_info

#include <just_larger.hpp>

int main()
 {
  just_larger<char> z;

  std::cout
   // use from type
   << sizeof(just_larger<char>) << std::endl

   // use from variable
   << typeid(z).name() << std::endl
   << sizeof(decltype(z)) << std::endl
   << typeid(just_larger<decltype(z)>).name() << std::endl
   << sizeof(just_larger<decltype(z)>) << std::endl
   ;

  return 0;
 }

The typeid operator returns a (const) reference on a std::type_info, a class that holds some information on the type. Unfortunately, name() doesn’t print pretty names, but some implementation-specific string: int is not printed as int but as i. That’s somewhat cryptic, but enough to verify that the implementation works correctly.

*
* *

We could overload just_larger with just anything, not just integral types. One evident generalization would be from float to double, but it can be anything that makes sense for your application. Also, maybe just_larger needs a companion template much_larger, that could ensure that large sums a given type would not overflow.


Storage size from bits

29/03/2016

Last week, we had a look at the computation of Log2 using templates and constexpr. Of course, I had ulterior motives. In particular, I was interested in allocating just the right number of bits for a field in a bit field, but rather than hard-coding it, having it deduced from a template argument. Let’s see how we can do that.

Read the rest of this entry »


Log2 (with C++ metaprogramming)

22/03/2016

C++ meta-programming a powerful tool. Not only can you use it to build generic types (such as the STL’s std::list), you can also use it to have compile-time evaluation. Let’s have a look at a simple problem that can be solved in two very different ways: computing the Log base 2 of an integer.

Read the rest of this entry »