A-Algorithm
A.off-by-one
An A.off-by-one error occurs when the code performs a calculation or includes an expression that is one away from what it should have been, which results in the code processing the wrong number of pieces of data, or returning a value that is incorrect, or taking a branch in the code at the wrong time. "One" can refer to 1 byte, but it can also mean one element in an array, one record in a file, and so on.
A well-known A.off-by-one error is the fencepost error. The canonical fencepost error occurs when calculating the number of posts in a 100-foot fence with a post every 10 feet. Your first guess might be 10, but that is incorrect. (You can also reverse the question by describing a fence with a post every 10 feet and 11 posts in all, and asking how long the fence is.)
So, a fencepost error occurs when the number of elements is miscounted because of neglecting to account for the final element (or the initial element). For example, code such as the following
// count how many pages will be printed
pagecount = lastpagenumber - firstpagenumber;
contains a fencepost error.
Another A.off-by-one error involves using the wrong comparison operator, confounding < and <= or > and >=. The following code, which tries to check if someone is old enough to vote in the United States (you must be 18 or older to vote), is an example of this:
if (age > 18) {
// OK to vote!
}
In languages that index arrays from 0, code can incorrectly start at the element with index 1 (the second element, that is). This error is sometimes considered an A.off-by-one error, but because those bugs typically involve processing the data, they are classified here as D.index.
A.logic
An A.logic error occurs if the programmer has designed a logically incorrect way to achieve the desired result.
In many cases, the error involves the incorrect calculation of a value based on some data. Often, this is caused by a bad assumption about the data in question. For example, the following code attempts to lowercase a string using knowledge of how characters are represented in ASCII. (The Python function ord() converts a character to its numeric ASCII value, while chr() does the reverse.)
upper = ""
for k in range(0, len(s)):
upper += chr(ord(s[k]) - ord("A") + ord("a"))
The code fails because the conversion algorithm is only correct if s[k] is an uppercase character. It won't work properly for spaces, lowercase characters, and so on.
Loops can also be prone to A.logic errors, especially the code to terminate the loop. Loops usually terminate when a logical expression changes from true to false or vice versa. One error is a loop termination condition that never changes:
for (j = 1; j != 100; j = j + 2)
Because j has an initial value of 1 and is incremented by 2 for each iteration, it never equals exactly 100, the logical expression j != 100 is always true, and the loop never terminates (unless j is modified somewhere within the loop body, or the code exits the loop through another method).
Code can also break out of a loop at an incorrect time, or neglect to break out at the proper time:
while (1) {
if (end_of_line) {
cleanup();
// probably missing a break statement here
}
// more processing
}
The previous examples could be fixed with minor changes. In other cases, the logic is simply flawed in a more general way, and needs to be redone. This code attempts to walk through an array and find the difference between the two values that are furthest apart (Math.abs() is a Java library function that calculates absolute value):
biggest = 0;
for (k = 0; k < a.length-1; k++) {
distance = abs(a[k] - a[k+1]);
if (distance > biggest) {
biggest = distance;
}
}
The code does what the programmer intended, but the algorithm is incorrect. It assumes the two values that are farthest apart will be in adjacent elements of the array, which isn't necessarily true. This code can't be saved with a small adjustment; it needs to be fundamentally reworked.
A.validation
Many blocks of code that need to be debugged are functions that take parameters passed from other code. Often, the function documentation restricts the range of values allowed for certain parameters. For example, a function that takes an argument percent might specify that the value should be between 0 and 100.
The compiler usually does not check such restrictions (depending on how they are specified), and the question becomes whether checking the validity of arguments should be part of the function's algorithm-in other words, whether parameters should be checked for validity within the function or if it is the caller's responsibility to ensure that parameters are valid before calling the function. If the function is supposed to check this, not having this code is a bug in the algorithm. (As previously mentioned, Knuth has a separate category, Robustness, which arguably includes such parameter checking, although he does not present it as such.)
A standard example is a function that is passed a pointer to a string. A function that was supposed to do nothing on an empty string might have code to check the validity of the string that was passed in:
void my_function(char * my_string) {
if (my_string == NULL) {
return;
}
if (strlen(my_string) == 0) {
return;
}
}
Nobody would argue about the second check, about the length of the string. Clearly, the function should check that. The first check, about the pointer being NULL, is there on the theory that the function is more robust if it makes that check, but of course, there are plenty of "not NULL but still invalid" pointer values that would make the function crash. (NULL just happens to be a common invalid value.) Calling the function as follows
my_function((void *)0x12345)
probably still causes a crash.
The extra check doesn't take much time to execute. On the other hand, it does add code that needs to be processed by the brain of the person reading it. The good news is it can usually be dismissed quickly, unless the code has the classic C/C++ error in it, of using = instead of == for a comparison:
if (my_string = NULL) {
return;
}
The question of "who should check for an invalid pointer" is one this book doesn't discuss. In the interest of simplifying the code and saving space in the source code listing, in general, the examples don't have validation code such as what's shown here, and this book doesn't have any A.validation bugs in its examples.
A.performance
Performance problems occur when a program performs its task properly, but uses far more resources than it needs. Often, the resource is time, but it could also be memory, disk space, network packets, or any other limited resource.
Because different programmers can solve the same problem with different algorithms and one of them is likely faster than the other, the question of when inferior performance becomes a bug is highly subjective. If the code is 10% larger than it could be, that is often not an issue, unless memory use is critically important. On the other hand, a program that is 100 times slower than necessary is generally considered to have a performance problem, no matter what the situation.
Knuth, when categorizing the performance fixes he made to TeX, listed them as enhancements, not bugs. As he noted, "I felt guilty when fixing the bugs, but I felt virtuous when making the enhancements."
Performance problems are included in this list for completeness. None of the bugs in the book are A.performance bugs.
| 
