How can I iterate over a string in 128-bit chunks?

Question

I have a function that operates on 128-bit blocks of data from an arbitrary-length string. If the string is not evenly divisible into chunks of 128 bits, it will be padded accordingly.

The purpose is to transform the data in the string that is fed into the function.

I initially thought of looping through the string a such:

//This might have stupid errors.  Hopefully it stillg gets the point across.
for (int i = 0; i < strn.size(); i += 16)
{
    string block = strn.substr(i, i + 15);
    strn.replace(i, i + 15, block);
}

I guess this would work, but I'm thinking there must be a more elegant way to do this. One idea that came to mind was to encapsulate strn in a class and implement my own iterator that can read its contents in 128-bit chunks. This is appealing because the constructor could handle padding and some of the functions I currently use could be made private, thus avoiding potential misuse. Does this seem like a fruitful approach? If so, how does one go about implementing his own iterator? Detailed explanations are most welcome, as I'm very inexperienced with C++.

Are there other, perhaps better, approaches?

Thanks!

SomeWittyUsername · Accepted Answer · 2012-11-06T17:08:27.677

3

There are many approaches. One of the more simple and straightforward ones would be like this: you can create your own type sized exactly 128 bit; simple struct will do the job.

typedef struct
{
    char buf[16];
} _128bit;

And use it to iterate over your string. Cast the beginning of your string to this struct type:_128bit* start = (_128bit*)buffer; and start iterating with it, using the integral pointer arithmetic. All operations on start will operate in terms of its size. E.g. ,start++ will move 128 bits forward; start-- will move 128 bit back. Once you're at the desired position, recast it to the desired type and perform your manipulations.

edited Nov 06 '12 at 17:08

answered Nov 06 '12 at 17:02

SomeWittyUsername

18,025
3
42
85

That sounds like a simple and elegant approach! Just a few questions: 1) Is there a reason for the underscore in `_128bit`? 2) Why the typedef? I'm guessing this allows me to cast other variables and constants as its type... is my inuition correct? 3) How is it that the `++` operator is already overloaded in this example? Why don't I have to do it explicitly? Many thanks and many apologies for my ignorance of finer C++ constructs! =) – Louis Thibault Nov 06 '12 at 17:10
1

1. If I recall correctly, variables names can't begin with a digit. 2. Hmm, no need actually in C++, in C this can shorten the code :). 3. That's the advantage of pointer arithmetic, it operates in terms of the pointed elements, see here for more details: http://stackoverflow.com/questions/394767/pointer-arithmetic BTW, this is a pure C solution, no C++ features used – SomeWittyUsername Nov 06 '12 at 17:13
Ok that makes sense. I'm still a bit unclear on the bit about typedefs, though. Doesn't the `typedef` keyword allow you to create a new type name? As such, shouldn't your example specify a name for the structure you've defined? ... something like `typedef struct{...}` ? – Louis Thibault Nov 06 '12 at 17:25
That's exactly what it does: `typedef struct {/* new type definition */} new_type_name;` – SomeWittyUsername Nov 06 '12 at 17:27
@icepick, *facepalm*. Yes, yes... you're absolutely right! Thank you for the help! – Louis Thibault Nov 06 '12 at 17:29
@icepick, Sorry, one last question! How should I do bounds checking in this case? That is, how should I make sure I don't iterate past the end of the string? – Louis Thibault Nov 06 '12 at 17:37
Express the length of the string in terms of 128bit elements and iterate up to it: `strlen(str)/sizeof(_128bit)`. – SomeWittyUsername Nov 06 '12 at 17:47

Mark B · Answer 2 · 2012-11-08T15:35:06.543

I would probably do this with iterators rather than indexing, still using your own for loop:

const int NUM_BITS_IN_CHUNK = 128;
const int CHUNK_SIZE = NUM_BITS_IN_CHUNK / CHAR_BIT;

for(std::string::const_iterator iter = str.begin(); iter < str.end(); iter += CHUNK_SIZE)
{
    your_func(iter, iter + CHUNK_SIZE);
}

The boost::iterator_adaptor code would look something like this. Note that I'm only getting four bytes per chunk instead of 16 for simplicity in the example.:

#include <iostream>
#include <string>

#include <boost/iterator_adaptors.hpp>

struct string_chunk_iterator : public boost::iterator_adaptor<string_chunk_iterator, std::string::const_iterator>
{
    string_chunk_iterator(const std::string::const_iterator& base) : iterator_adaptor(base) { }

private:
    friend class boost::iterator_core_access;
    void increment() { this->base_reference() = this->base() + 4; }
    void advance(typename iterator_adaptor::difference_type n)
    {
        this->base_reference() = this->base() + (4 * n);
    }
};

int main()
{
    const std::string tester(20, 'A');

    string_chunk_iterator iter(tester.begin());
    string_chunk_iterator str_end(tester.end());

    for(; iter != str_end; ++iter)
    {
        std::string chunk(&*iter, &*(iter + 1));

        std::cout << chunk << std::endl;
    }

    return 0;
}

Is there a way to subclass `std::string::const_iterator` such that incrementing it with `++` or calling `iter.next()` will increment by 128 bits? Also, I'm a bit confused. I would have thought that `iter += 128` would move the pointer 128 *bytes* (or indexes). What am I missing? — Louis Thibault, Nov 07 '12 at 21:30
@blz I believe you could use `boost::iterator_adapter` to create such an iterator, but I have little experience with that part of boost. You're correct that `iter += 128` would indeed increment by 128 bytes. Luckily, that's not what I'm doing in my code: I'm incrementing by 16 (bytes). That's why I created the constants, to make sure that it still works even on say a system with 16 bit `char`. — Mark B, Nov 07 '12 at 23:37

How can I iterate over a string in 128-bit chunks?

2 Answers2