# Split string into “n” lengths with padding

I quickly wrote a short program to split a string into $n$ lengths with variable-character padding:

#include <iostream>
#include <algorithm>

std::string getString();
int getBlockSize();
std::string tokenize(std::string str, int blockSize);

int main(){
std::string str = getString();
int blockSize = getBlockSize();

str.erase(std::remove(str.begin(), str.end(), ' '), str.end());
str = tokenize(str, blockSize);

std::cout << str;

std::cout << '\n';
return 0;
}

std::string getString(){
std::cout << "Input string: ";

std::string str;
std::getline(std::cin, str);

return str;
}

int getBlockSize(){
std::string inputStr;
int blockSize;

do{
try{
std::cout << "Block size: ";
std::getline(std::cin, inputStr);
blockSize = std::stoi(inputStr);
} catch(...){
blockSize = 0;
}
} while(blockSize < 1);

return blockSize;
}

do{
std::cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n');
} while(std::cin.fail());

}

while(str.length() % blockSize != 0){
}
return str;
}

std::string tokenize(std::string str, int blockSize){
for(int i = blockSize; i < str.length(); i += blockSize+1){
str.insert(i, 1, ' ');
}
return str;
}


This code firstly gets the input string (str), gets the size of the block (blockSize), and then gets the character that is to be used as padding (paddingChar).

It then removes all spaces from input string, adds padding, and then tokenizes the string by splitting it into blockSize pieces.

Example output:

Input string: Tis' but a scratch!
Block size: 11
Tis'butascr atch!XXXXXX


The splitting of a stream of characters into blocks is common in cryptography. While there certainly are many, many Code Review questions on tokenization, I was unable to find one that was exactly like this and in C++, so I felt that this area should also be covered in that aspect.

I tried to use the helpful suggestions from my previous Code Review questions to improve the quality of my code as best I could. Despite that, there is always room to improve the way that I write code.

How can I improve this code?

• isn't this algorithm lossy? i.e. how do you recover the original plaintext? – Richard Hodges Jan 16 '17 at 11:45
• @RichardHodges The message is still decipherable by a human, i.e. you can still tell that the message Tis'butascr atch!XXXXXX is meaning Tis' but a scratch!. This type of classical cryptography is mainly used as a first step before something like columnar transposition. But you're right, it isn't meant for a computer to recover the plaintext, that would be much harder. – esote Jan 16 '17 at 16:53

My first impression is that we would probably wish to avoid copying and shuffle data as much as possible.

The code as presented does the following:

1. conditionally remove items (worst case time complexity occurs when every char is a space, in which case it's $\mathcal{O}(\frac{n^2}{2})$ (more or less))

2. append padding (worst case will involve a reallocation plus copy $\mathcal{O}(n)$)

I think we can do better, performing the entire operation in linear time and guaranteeing no memory reallocations. This involves iteratively conditionally copying the bytes. We can do this because std::string's iterators are random-access, so we can compute distances in constant time.

I have presented it here as a simple composition of methods in a lightweight engine object. Another way would be to create a state machine which could be chained to another encryption stage:

#include <iostream>
#include <algorithm>

struct squish_engine
{
: blockSize(blockSize)
{

}

// useful for initial allocation of destination string
std::size_t estimate_size(std::size_t plaintext_length) const {
return plaintext_length + blockSize;
}

// a predicate
static bool matchesSpace(char c) {
return c == ' ';
}

// operation in terms of iterators
template<class FromIter, class ToIter>
ToIter operator()(FromIter first, FromIter last, ToIter first2) const
{
// use stl algorithms where possible
auto last2 = std::remove_copy_if(first, last, first2, matchesSpace);
auto pads = std::distance(first2, last2) % blockSize;
}
return last2;
};

// this is the public interface
template<class Iter>
std::string operator()(Iter first, Iter last) const
{
// build an overly-large string to accept the result.
// we may as well pad it now, as it's no extra cost compared
// to zero-filling
// our internal operator will compute the end point of the
auto last2 = (*this)(first, last, std::begin(result));

// so we can simply truncate any padding chars we don't need
result.erase(last2, result.end());

// and return the cypher
return result;
}

// convenience interface
std::string operator()(const std::string& s)
{
return (*this)(std::begin(s), std::end(s));
}

std::size_t blockSize;
};

// the concept of making a copy while filtering
template<class Filter>
std::string filter_copy(const std::string& source, Filter&& filter)
{
return filter(source);
}

int main(){

std::size_t blockSize = 11;