Right, I found the bug! And as I was expecting, some pixels were getting overwritten. The problem is in the embedByte function, specifically, in the conditions of the for loops.
for(int i=startX; i<maxX && count<8; i++) {
for(int j=startY; j<maxY && count<8; j++) {
Each loop will iterate until you either reach the end of the row/column or the count reaches 8. The problem arises when you terminate because the end of the row/column has been reached. To demonstrate this, this is what happens for your image.
The first character is embedded in pixels (0, 32), (0, 33), ..., (0, 39). This is all straightforward until you reach the 11th character, where you get the following.
(0, 112)
(0, 113)
(0, 114)
(1, 112)
(1, 113)
(1, 114)
(2, 112)
(2, 113)
The reason for this mess is at (0, 114). At j=114, the j loop has reached its limit and exits. Since count is not 8 yet, we go back to the i loop, which increments by 1 and then enters the j loop again, which starts at startY=112. This explains (1, 112) and what comes next. These pixels shouldn't have been changed yet, since they will be overwritten during the 25th character (normally written for the first time). Instead, you should have gotten this:
(0, 112)
(0, 113)
(0, 114)
(1, 0)
(1, 1)
(1, 2)
(1, 3)
(1, 4)
To achieve this, once you have reached the edge with j, you want to reset startY. You can do this by adding the following code inside the j loop.
if(j==maxY-1) {
startY = 0;
}
Similarly, you want to add this correction in the extractByte function for the decoding process.
Observation
Since you can fit approximately 14 characters in 115 pixels, this is when the problem arises. This explains the 11 -> 25 -> 39. By coincidence, the sharing pixels that 11 and 25 write, embed the same bit and the bug is not expressed. But with the introduction of 39, 25 is affected.
