The Origins of Malloc
The 1973 Fourth Edition Unix kernel source code contains two routines, malloc and mfree, that manage the dynamic allocation and release of main memory blocks for in-memory processes and of continuous disk swap area blocks for swapped-out processes. Their implementation and history can teach us many things regarding modern computing.
Continue reading "The Origins of Malloc"
Of BOOL and stdbool
The C99 standard has added to the C programming language a Boolean type,
Continue reading "Of BOOL and stdbool"
_Bool and the
bool alias for it. How well does this type interoperate with the Windows SDK
BOOL type? The answer is, not at all well, and here's the complete story.
Programming Languages vs. Fat Fingers
A substitution of a comma with a period in project Mercury's working Fortran code compromised the accuracy of the results, rendering them unsuitable for longer orbital missions.
How probable are such events and how does a programming language's design affect their likelihood and severity?
In a paper I recently presented at the
4th Annual International Workshop on Evaluation and Usability of Programming Languages and Tools
I showed results obtained by randomly perturbing similar programs written in
diverse languages to see whether the compiler or run-time system
would detect those changes as errors,
or whether these would end-up generating incorrect output.
Continue reading "Programming Languages vs. Fat Fingers"
How to Calculate an Operation's Memory Consumption
How can you determine how much memory is consumed by a specific
operation of a Unix program?
Valgrind's Massif subsystem could help you in this regard,
but it can be difficult to isolate a specific operation from
Here is another, simpler way.
Continue reading "How to Calculate an Operation's Memory Consumption"
Applied Code Reading: Debugging FreeBSD Regex
When the code we're trying to
read is inscrutable,
inserting print statements and running various test cases can be
two invaluable tools.
Earlier today I fixed
a tricky problem in the FreeBSD regular expression library.
originally written by Henry Spencer in the early 1990s,
is by far the most complex I've ever encountered.
It implements sophisticated algorithms with minimal commenting.
Also, to avoid code repetition and increase efficiency,
the 1200 line long main part of the regular expression execution engine is
included in the compiled C code
three times after modifying various macros to adjust the code's behavior:
the first time the code targets small expressions and operates
with bit masks on long integers,
the second time the code handles larger expressions
by storing its data in arrays,
and the third time the code is also adjusted to handle multibyte characters.
Here is how I used test data and print statements to locate and fix the problem.
Continue reading "Applied Code Reading: Debugging FreeBSD Regex"
HP-200LX Remote Control Hacks
All my friends know that for the past 15 years I've been semi-attached
(recently updated to a 200LX)
for my personal information management and many other tasks.
The device is extremely versatile, sturdy, and flexible.
Amazingly, after so many years of hard daily use, I still find new
applications for it.
Continue reading "HP-200LX Remote Control Hacks"
Real-Time Google Earth GPS Tracking
In a recent trip I incorrectly assumed that real-time tracking of
Google Earth's pre-cached maps with a GPS receiver would be sufficient
help for navigating around the highways in Los Angeles.
I therefore experimented with the way Google Earth's
sparsely-documented real time tracking works,
and wrote a small program to interface Google Earth with a GPS receiver.
Fortunately, after seeing a colleague drive with a car-GPS device
on the dashboard I came to my senses, and got a real
Continue reading "Real-Time Google Earth GPS Tracking"
The Escape of a Small Program
C. A. R. Hoare's
Law of Large Programs states that
inside every large program is a small program struggling to get out.
The parking receipt I got yesterday returning from a
SQO-OSS meeting proves this fact.
Continue reading "The Escape of a Small Program"
When I set out to apply CScout
on the Linux kernel source code, I
discovered that it failed to correctly expand a couple of C macros,
causing the analysis to fail. This prompted me to reimplement CScout's
macro expansion using a
precise functional specification,
the code's severe degradation in time performance, and finally tidy up
the optimized code mess.
Continue reading "Code Finessing"
The Verbosity of Object-Oriented Code
As I refactored a piece of code from an imperative to an
object-oriented style I increased its clarity and reusability,
but I also trippled its size.
This worries me.
Continue reading "The Verbosity of Object-Oriented Code"
Dave Prosser's C Preprocessing Algorithm
For about five years I've been trying to implement a fully conforming
C preprocessor for the front end of the
CScout refactoring browser.
I've found this to be a fiendishly difficult task.
Although what I have written can correctly process million-line
real-life projects, every once in a while I come across a construct
that confuses my implementation.
While searching the web for explanations of some of the finer points
of the C standard I came across a reference to an algorithm by
Dave Prosser that the X3J11 (ANSI C standard) committee used as a basis
for the standard's wording.
Continue reading "Dave Prosser's C Preprocessing Algorithm"
Interoperability Requires Temperance
After testing the CScout refactoring browser
on the FreeBSD kernel, I decided
to try it on Linux.
I'm getting there, but slowly, and the reason is the gratuitous use of
gcc extensions made in the Linux kernel source code.
Every time I come across a program construct that CScout doesn't
grok, I have to study the C standards to see if the construct is legal C
that CScout fails to implement or a gcc extension.
Extensions are trouble, because, they're typically only vaguely documented.
Continue reading "Interoperability Requires Temperance"
Code Quality: The Open Source Perspective
My new book
Code Quality: The Open Source Perspective
three years after I started writing it.
The book owes more to open source software than any of the books
dealing with Linux, PHP, Apache, Perl or any other book covering
a specific technology.
Continue reading "Code Quality: The Open Source Perspective"
A General-Purpose Swap Macro
A couple of days ago I came up with a general-purpose macro for swapping
values in C programs.
My colleague Panagiotis Louridas suggested an improvement, and
this prompted me to see the two macros got compiled.
Continue reading "A General-Purpose Swap Macro"
How to Sort Three Numbers
Quick: how do you sort three numbers in ascending order?
Continue reading "How to Sort Three Numbers"
Warum einfach, wenns auch kompliziert geht?
(Why make it simple, when you can also make it complicated?)
Consider the task of associating code with specific data
Using a multi-way conditional can be error-prone, because
the data values become separated by the code.
It can also be inefficient in the cases where we have to use cascading
Continue reading "Warum einfach, wenns auch kompliziert geht?"
else if statements, instead of a
which the compiler can optimize into a hash table.
In C I would use an array containing values and function pointers.
My understanding is that the Java approach involves using the
Strategy pattern: a separate class for each case,
and an interface "to rule them all".
Macro-based Substitutions in Source Code
A friends asks:
"How can one easily replace a method call (which can contain
arguments with brackets in its invocation code) with a simple
Continue reading "Macro-based Substitutions in Source Code"
The hypot() Mystery
I was writing a section for the
followup volume, and wanted to demonstrate the pitfalls of
using homebrewn mathematical functions instead of the library
As an example, I chose to compare the C library
Continue reading "The hypot() Mystery"
sqrt(x * x, y * y).
I created a plot of "unit in last place" (ulp) error values between
the two functions, which demonstrated how the error increased for larger
values of y.
Patching Framework III
I needed to read some old files I wrote in 1992 using the Ashton-Tate
Framework III program.
Unfortunately, trying to run the program under Windows XP resulted in a
Continue reading "Patching Framework III"
Divide overflow" error.
A bit of searching on the web revealed that the problem was related
to the system's speed (1.6GHz).
Apparently, Framework tries to calculate the speed of the machine
by dividing a fixed number with a loop counter;
on modern machines this results in the overflow.
Computer Languages Form an Ecosystem
(This is a copy of an
article I posted on
slashdot on March 15th,
in response to a discussion titled
C Alive and Well Thanks to Portable.NET.
Many posters argued that the C language is dead.
I add my response here, because one month after its original slashdot submission,
I am still getting web site hits from it.)
Continue reading "Computer Languages Form an Ecosystem"