Movatterモバイル変換

Our long effort to rebuild Cocoa piece by piece continues. For today, reader Nate Heagy has suggested buildingNSString'sstringWithFormat: method.

String Formatting
It's hard to get very far in Cocoa without knowing about format strings, but just in case, here's a recap.

stringWithFormat:, as well as other calls likeNSLog, take strings that can use special format specifiers of the form%x. The% indicates that it's a format specifier, which reads an additional argument and adds it to the string. The character after it specifies what kind of data to display. For example:

[NSStringstringWithFormat:@"Hello, %@: %d %f",@"world",42,1.0]

This produces the string:

Hello,world:421.0

This is useful for all sorts of things, from creating user-visible text, to making dictionary keys, to printing debug logs.

Variable Arguments
This method takes variable arguments, which is an odd corner of C. For more extensive coverage of how to write such methods, seemy article on vararg macros and functions. Here's a quick recap.

You declare the function or method to take variable arguments by putting... at the end of the parameter list. For a method, this ends up being slightly odd syntax:

+(id)stringWithFormat:(NSString*)format,...;

That, ... thing at the end is actually legal Objective-C.

Once in the method, declare a variable of typeva_list to represent the variable argument list. Theva_start andva_args macros initialize and clean it up. Theva_arg macro will extract one argument from the list and return it.

Code
As usual, I have posted the code on GitHub. You can view the repository here:

https://github.com/mikeash/StringWithFormat

This code supports an extremely limited subset of the fullNSString formatting functionality.NSString supports a huge number of specifiers, as well as options such as field width, precision, and out-of-order arguments. My reimplementation sticks to a basic set that's enough to illustrate what's going on. In particular, it supports:

• %d -int
• %ld -long
• %lld -long long
• %u,%lu, and%llu, for the unsigned variants of the above.
• %f -float
• %s - C strings
• %@ - Objective-C objects
• %% - Output a single% character.

Furthermore, no options are supported.

Interface
For my reimplementation, I wrote a function calledMAStringWithFormat that does the same thing as[NSString stringWithFormat:]. However, I wrapped the meat of the implementation in a class to organize the various bits of state needed. That function just makes ava_list for the arguments, instantiates a formatter, and asks it to do the work:

NSString*MAStringWithFormat(NSString*format,...){va_listarguments;va_start(arguments,format);MAStringFormatter*formatter=[[MAStringFormatteralloc]init];NSString*result=[formatterformat:formatarguments:arguments];va_end(arguments);returnresult;}

TheMAStringFormatter class essentially carries out two tasks in parallel. First, it reads through the format string character-by-character, and secondly, it writes the resulting string. Accordingly, it has two groups of instance variables. The first group deals with reading through the format string:

CFStringInlineBuffer_formatBuffer;NSUInteger_formatLength;NSUInteger_cursor;

CFStringInlineBuffer is a little-known API inCFString that allows for efficiently iterating through the individual characters of a string. Making a function or method call for each character is slow, soCFStringInlineBuffer allows fetching them in bulk for greater efficiency. The length of the format string is stored to avoid running off the end, and the current position within the format string is stored in_cursor.

The second group deals with collecting the output of the formatting operation. It consists of a buffer of characters, the current location within that buffer, and its total size:

unichar*_outputBuffer;NSUInteger_outputBufferCursor;NSUInteger_outputBufferLength;

This could be implemented using anNSMutableData orNSMutableString, but this is much more efficient. While this code isn't intended to be particularly fast in general, I just couldn't stand the thought of making each character run through a call to a string object.

Reading
MAStringFormatter has aread method which fetches the next character from_formatBuffer, and returns-1 once it reaches the end of the string. There isn't a whole lot to this, just anif check and a call toCFStringGetCharacterFromInlineBuffer:

-(int)read{if(_cursor<_formatLength)returnCFStringGetCharacterFromInlineBuffer(&_formatBuffer,_cursor++);elsereturn-1;}

Writing
Writing is a little more complex, because the size of the output string isn't known ahead of time. First, there's adoubleOutputBuffer method that increases the size of the output buffer. If the buffer is completely empty, it allocates it to hold64 characters. If it's already allocated, it doubles the size:

-(void)doubleOutputBuffer{if(_outputBufferLength==0)_outputBufferLength=64;else_outputBufferLength*=2;

Once the new buffer length is computed, a simple call torealloc allocates or reallocates the buffer:

_outputBuffer=realloc(_outputBuffer,_outputBufferLength*sizeof(*_outputBuffer));}

Next, there's awrite: method, which takes a singleunichar and appends it to the buffer. If the write cursor is already at the end of the buffer, it first increases the size of the buffer:

-(void)write:(unichar)c{if(_outputBufferCursor>=_outputBufferLength)[selfdoubleOutputBuffer];

Once sufficient storage is assured, it placesc at the current cursor position, and advances the cursor:

_outputBuffer[_outputBufferCursor]=c;_outputBufferCursor++;}

Formatting
Theformat:arguments: method is the entry point to where the real work gets done. The first thing it does is fill out the format string instance variables using theformat argument:

-(NSString*)format:(NSString*)formatarguments:(va_list)arguments{_formatLength=[formatlength];CFStringInitInlineBuffer((__bridgeCFStringRef)format,&_formatBuffer,CFRangeMake(0,_formatLength));_cursor=0;

It also initializes the output variables. This isn't necessary, strictly speaking, but leaves open the possibility of reusing a single formatter object:

_outputBuffer=NULL;_outputBufferCursor=0;_outputBufferLength=0;

After that, it loops through the format string until it runs off the end:

intc;while((c=[selfread])>=0){

All format specifiers begin with the'%' character. Ifc is not a'%', then just write the character directly to the output:

if(c!='%'){[selfwrite:c];}

This comparison uses the character literal'%' despite the fact thatread deals inunichar. This works because the first 128 Unicode code points map directly to the 128 ASCII characters. When aunichar contains a%, it contains the same value as the ASCII'%', and the same is true for any other ASCII character. This is terribly convenient when working with ASCII data inNSStrings.

Ifc is a'%' character, then there's a format specifier to come. What happens at this point depends on what the next character is:

else{intnext=[selfread];

If the format specifier is a'd', then it reads anint from the arguments and passes it to thewriteLongLong: method, which handles the actual work of formatting the value into the output. All signed integers pass through that method. Sincelong long is the largest signed data type handled, a single method that prints those will work for all signed types:

if(next=='d'){intvalue=va_arg(arguments,int);[selfwriteLongLong:value];}

If the format specifier is'u', then it does the same thing as above, but withunsigned, and calling through to thewriteUnsignedLongLong: method:

elseif(next=='u'){unsignedvalue=va_arg(arguments,unsigned);[selfwriteUnsignedLongLong:value];}

Note thatint andunsigned are the smallest integer types handled here. There is no code to handlechar orshort. This is because of C promotion rules for functions that take variable arguments. When passed as a variable arguments, values of typechar orshort are promoted toint, and likewise theunsigned variants are promoted tounsigned int. This means that the code forint handles the smaller data types as well, without any additional work.

If the next character is'l', then we need to keep reading to figure out what to do:

elseif(next=='l'){next=[selfread];

If the character following the'l' is'd', then the argument is along. Follow the same basic procedure as before:

if(next=='d'){longvalue=va_arg(arguments,long);[selfwriteLongLong:value];}

Likewise, if the next character is'u', it's anunsigned long:

elseif(next=='u'){unsignedlongvalue=va_arg(arguments,unsignedlong);[selfwriteUnsignedLongLong:value];}

If the next character is'l' again, then we need to read one character further

elseif(next=='l'){next=[selfread];

Here,'d' indicates along long, and'u' indicates anunsigned long long. These are handle in the same fashion as before:

if(next=='d'){longlongvalue=va_arg(arguments,longlong);[selfwriteLongLong:value];}elseif(next=='u'){unsignedlonglongvalue=va_arg(arguments,unsignedlonglong);[selfwriteUnsignedLongLong:value];}}}

That's it for the deep sequence of'l' variants. Next comes a check for'f'. In that case, the argument is a `double', and gets passed off to a method built to handle that:

elseif(next=='f'){doublevalue=va_arg(arguments,double);[selfwriteDouble:value];}

Once again, promotion rules simplify things a bit. When afloat is passed as a variable argument, it's promoted to adouble, so no extra code is needed to handlefloat.

If the format specifier is an's', then the argument is a C string:

elseif(next=='s'){constchar*value=va_arg(arguments,constchar*);

This is simple enough not to need a helper method. It iterates through the string until it reaches the terminating0, writing each character as it goes. This assumes the string contains only ASCII:

while(*value)[selfwrite:*value++];}

If the format specifier is a'@', then the argument is an Objective-C object:

elseif(next=='@'){idvalue=va_arg(arguments,id);

To find out what to output, ask the value for its description:

NSString*description=[valuedescription];

The length of the description is also handy:

NSUIntegerlength=[descriptionlength];

Now, copy the contents ofdescription into the output buffer. I decided to get a bit fancy here. A simple loop could suffice, perhaps usingCFStringInlineBuffer for speed, but I wanted something nicer. AnNSString can put its contents into an arbitrary buffer, so why not askdescription to put its contents directly into the output buffer? To do that, the output buffer must first be made large enough to containlength characters:

while(length>_outputBufferLength-_outputBufferCursor)[selfdoubleOutputBuffer];

Doing this in awhile loop is mildly inefficient ifdescription is larger than the buffer is already. However, that's an uncommon case, and the code is nicer by being able to sharedoubleOutputBuffer, so I decided to use this approach.

Now that the output buffer is sufficiently large, usegetCharacters:range: to dump the contents ofdescription into it, putting it at the location of the output cursor:

[descriptiongetCharacters:_outputBuffer+_outputBufferCursorrange:NSMakeRange(0,length)];

Finally, move the cursor past the newly written data:

_outputBufferCursor+=length;}

We're nearly to the end. If the character following the'%' is another'%', that's the siganl to write a literal'%' character:

elseif(next=='%'){[selfwrite:'%'];}}}

That's the last case handled by this miniature implementation. Once the loop terminates, the resultingunichars are located in_outputBuffer, with_outputBufferCursor indicating the number ofunichars in the buffer. Create anNSString from it and return the new string:

NSString*output=[[NSStringalloc]initWithCharactersNoCopy:_outputBufferlength:_outputBufferCursorfreeWhenDone:YES];returnoutput;}

Using theNoCopy variant makes this potentially more efficient, and removes the need to manuallyfree the buffer.

That's the basic shell of the formatting code. To complete it, we need the code to print signed and unsignedlong longs, and code to printdoubles.

unsigned long long
Let's start with the most fundamental helper method,writeUnsignedLongLong:. The others ultimately rely on this one for much of their work.

The algorithm is simple: divide by successive powers of ten, produing a single digit each time. Convert the digit to aunichar and write it.

We'll store the power of ten in a variable calledcursor and start it at1:

-(void)writeUnsignedLongLong:(unsignedlonglong)value{unsignedlonglongcursor=1;

However, what we really want is the power of ten with as many digits as the input number. For example, for42, we want10. For123456, we want100000. To obtain this, we just keep multiplyingcursor by ten until it has the same number of digits asvalue, which is easily tested by seeing ifvalue is less than ten times larger thancursor:

while(value/cursor>=10)cursor*=10;

Now we just loop, dividingcursor by ten each time, until we run out ofcursor:

while(cursor>0){

The current digit is obtained by dividingvalue bycursor:

intdigit=value/cursor;

To compute theunichar that corresponds withdigit, just add the literal'0' character. ASCII (and therefore Unicode) lays out digits sequentially starting with'0', making this easy:

[selfwrite:'0'+digit];

With the digit written, we remove it fromvalue, then movecursor down:

value-=digit*cursor;cursor/=10;}}

And just like that, the value flows into the output. This code even correctly handles zero, due to ensuring thatcursor is always at least1.

long long
ThewriteLongLong: method is simple. If the number is less than zero, write a'-' and negate the number. For positive numbers, do nothing special. Pass the final non-negative number towriteUnsignedLongLong:.

-(void)writeLongLong:(longlong)value{unsignedlonglongunsignedValue=value;if(value<0){[selfwrite:'-'];unsignedValue=-unsignedValue;}[selfwriteUnsignedLongLong:unsignedValue];}

There's an odd corner case in here. Due to the nature ofthe two's complement representation of signed integers, the magnitude of the smallest representablelong long is one greater than the magnitude of the largest representablelong long on systems we're likely to encounter.

Along long on a typical system can hold numbers all the way down to-9223372036854775808, but only up to9223372036854775807. This means you can't negate the smallest possible negative number and get a positive number, because the data type can't hold the appropriate positive number. If you try to negate-9223372036854775808, you get an overflow and undefined behavior, although the result is usually just-9223372036854775808 again.

However, negation is well defined on allunsigned values, and it has the same bitwise result as negation on the bitwise-equivalent signed values. In other words,-signedLongLong produces the same bits as-(unsigned long long)signedLongLong. It also works on the bits that make up-9223372036854775808, and produces9223372036854775808. By movingvalue intounsignedValue and then negating that, the above code works around the problem of undefined behavior when negating the smallest representablelong long.

double
Now it's time for the really fun one. Due to the nature of floating-point arithmetic, figuring out how to properly and accurately print the value of adouble was pretty tough. I did some research, even dove into an open-source implementation ofprintf to see how they did it, but it was so crazy and incomprehensible that I didn't get too far. I finally settled on a technique which works fairly well, and I think is as accurate as the data type allows, although the output tends to have more digits than it strictly needs.

The first step in solving the problem is to break it into two pieces. I split the double into the integer part and the fractional part, then deal with each one separately. Print each part in base 10, separate the two with a dot, and done.

The trick, then, is how to print the integer and fractional parts in base 10. I didn't want to use the same technique of successive division that I used forunsigned long long, because I was concerned that it would lose accuracy. There are integers that can be represented in adouble, but where the result of dividing the integer by ten can't be exactly represented in adouble. Similarly, I was afraid that the equivalent successive multiplication by ten for the fractional part would lose precision.

However, dividing or multiplying a double by two to move isalways safe, unless it pushes it beyond the limits of what can be represented. If you only do this to push it closer to1.0, then it will never lose precision. Furthermore, it's possible to chop off the fractional part of a double without losing precision in the integer part, and vice versa. Put together, these operations allow extracting information from adouble bit by bit, which is enough to compute an integer representation of its integer and fractional parts. With those in hand, the existingwriteUnsignedLongLong: method can be used to print the digits.

With this in mind, I set off. The first step is to check for negative values. Ifvalue is negative, write a'-', and negate it:

-(void)writeDouble:(double)value{if(value<0.0){[selfwrite:'-'];value=-value;}

Unlike thelong long case, there are nodouble values less than0.0 that can't be safely and correctly negated, so no shenanigans are needed here.

Next, check for infinity and NaN, and short circuit the whole attempt for them:

if(isinf(value)||isnan(value)){constchar*str=isinf(value)?"INFINITY":"NaN";while(*str)[selfwrite:*str++];return;}

If the number is an actual number, extract the integer and fractional parts.

doubleintpart=trunc(value);doublefracpart=value-intpart;

With those in hand, call out to helper methods to write those two parts, separated by a dot:

[selfwriteDoubleIntPart:intpart];[selfwrite:'.'];[selfwriteDoubleFracPart:fracpart];}

Integer Part
Writing the integer part is the simpler of the two, conceptually. The strategy is to shift thedouble value one bit to the right until the value becomes zero. Each bit that's extracted is added to anunsigned long long accumulator. Once thedouble becomes zero, the accumulator contains its integer value.

The one tricky part is how to handle the case where thedouble contains a value that's larger than anunsigned long long can contain. To handle this, whenever the value of the current bit extracted from thedouble threatens to overflow, the accumulator is divided by ten to shift it rightwards and allow more room. The total number of shifts is recorded, and the appropriate number of extra zeroes are printed at the end of the number. Dividing the accumulator by ten loses precision, but the 64 bits of anunsigned long long exceeds the53 bits of precision in adouble, so the lost precision should not actually result in incorrect output. At the least, while the output may not precisely match the integer value stored in thedouble, it will be closer to that value than to any other representabledouble value, which I'm calling close enough.

In order to know when the accumulator threatens to overflow, the code needs to know the largest power of ten that can be represented in anunsigned long long. This method computes it by just computing successive powers of ten until it gets close toULLONG_MAX:

-(unsignedlonglong)ullongMaxPowerOf10{unsignedlonglongresult=1;while(ULLONG_MAX/result>=10)result*=10;returnresult;}

ThewriteDoubleIntPart: method starts off by initializing atotal variable to zero:

-(void)writeDoubleIntPart:(double)intpart{unsignedlonglongtotal=0;

This is the accumulator that will hold the total computed value so far. It also keeps track of the value of the current bit:

unsignedlonglongcurrentBit=1;

This is multiplied by two each time a bit is extracted from thedouble, and represents the value of that bit.

The maximum value that can be stored intotal before overflow threatens is cached:

unsignedlonglongmaxValue=[selfullongMaxPowerOf10]/10;

This is one digit less than the maximum representable power of ten, in order to make sure that it can never overflow the accumulator. There is a surplus of 11 bits of precision in the accumulator, so losing one digit doesn't hurt too much.

The number of times thattotal andcurrentBit have been shifted to the right is recorded so that the appropriate number of trailing zeroes can be output later:

unsignedsurplusZeroes=0;

Setup is complete, now it's time to loop untilintpart is exhausted:

while(intpart){

A bit is extracted fromintpart by dividing it by two:

intpart/=2;

Becauseintpart contains an integer, dividing it by two produces a number with a fractional part that is either.0 or.5. The.5 case represents a one bit that needs to be added tototal. The presence of.5 is checked by using thefmod function, which computes the remainder when dividing by a number. Usingfmod with1.0 as the second argument just produces the fractional part of the number:

if(fmod(intpart,1.0)){

If the bit is set, thencurrentBit is added tototal, and the.5 is sliced off ofintpart using thetrunc function:

total+=currentBit;intpart=trunc(intpart);}

Next,currentBit is multiplied by two so that it holds the right value for the next bit to be extracted:

currentBit*=2;

IfcurrentBit exceedsmaxValue, then bothcurrentBit andtotal get divided by ten, andsurplusZeroes is incremented. Both are rounded when dividing by adding5 to them first, to aid in preserving as much precision as possible:

if(currentBit>maxValue){total=(total+5)/10;currentBit=(currentBit+5)/10;surplusZeroes++;}}

Onceintpart is exhausted,total contains an approximation of its original value, andsurplusZeroes indicates how many times it got shifted over. First, it printstotal:

[selfwriteUnsignedLongLong:total];

Finally, it prints the appropriate number of trailing zeroes:

for(unsignedi=0;i<surplusZeroes;i++)[selfwrite:'0'];}

Fractional Part
The basic idea for printing the fractional part is similar to printing the integer part. The difference is that the accumulator can't directly represent the fractional value, becauseunsigned long long doesn't do fractions. Instead, it holds the fractional value, scaled up by some large power of ten. For example,100 might represent1.0, in which case the value of the first bit in the fractional part of adouble is50, the second bit is25, and so forth. The actual numbers used contain a lot more zeroes at the end.

The accumulator for the integer part can overflow, while the accumulator for the fractional part canunderflow. If thedouble contains an extremely small value, the accumulator will end up containing zero, which is no good. A similar strategy is used to deal with this problem, but in the opposite direction: whenever the accumulator and current bit become too small, they are multiplied by ten, and an extra leading zero is output.

The method starts off with its accumulator initialized to zero:

-(void)writeDoubleFracPart:(double)fracpart{unsignedlonglongtotal=0;

The value of the current bit is started at the largest power of ten that will fit into anunsigned long long. This represents1.0, and will be divided by2 right away to properly represent0.5 for the first bit extracted from thedouble:

unsignedlonglongcurrentBit=[selfullongMaxPowerOf10];

The threshold for when the numbers become too small is the maximum representable power of ten, divided by ten. When this value is reached, there's a conceptual leading zero, and it's time to shift everything over:

unsignedlonglongshiftThreshold=[selfullongMaxPowerOf10]/10;

Now it's time for the loop. Keep extracting bits fromfracpart until there's nothing left:

while(fracpart){

fracpart is shifted to the left by one bit, whilecurrentBit is simultaneously shifted to the right:

currentBit/=2;fracpart*=2;

The integer part of the resulting number will be either1 or0. If it's1, the corresponding bit is1, so addcurrentBit tototal, and chop the1 offfracpart:

if(fracpart>=1.0){total+=currentBit;fracpart-=1.0;}

If both the accumulator andcurrentBit are belowshiftThreshold, it's time to shift everything over, and write a leading zero. Note that the number of shifts doesn't need to be tracked like it did in the previous method, because the leading zeroes can be written out immediately:

if(currentBit<=shiftThreshold&&total<=shiftThreshold){[selfwrite:'0'];currentBit*=10;total*=10;}}

Once the loop exits, there's one more task to be done.total now contains an integer representation of the decimal representation of the fractional part that was passed into the method (whew!), but with potentially a large number of redundant trailing zeroes. For example, iffracpart contained0.5, thentotal now contains5000000000000000000, but those trailing zeroes shouldn't be printed in the output. They're removed by just dividingtotal by ten repeatedly to get rid of trailing zeroes:

while(total!=0&&total%10==0)total/=10;

Once that's done,total is ready to print, so it's passed towriteUnsignedLongLong:

[selfwriteUnsignedLongLong:total];}

That's the end of the adventure of printing adouble.

Conclusion
stringWithFormat: is an extremely useful method that is, at its heart, a straightforward function that takes variable arguments. There are a ton of subtleties in how to output all of the various data formats, such as the adventure in printing adouble above. There are further complications in supporting all of the various options available in format strings, which the above code doesn't even address. However, it's ultimately a big loop that looks for'%' format specifiers, and usesva_arg to extract the arguments passed in by the caller. AlthoughstringWithFormat: is considerably more complex, you now have a basic idea of how it's put together.

That's it for today. Come back next time for more bitwise adventures. Friday Q&A is driven by reader suggesions, so until the next time, please keepsending in your ideas for topics.

Add your thoughts, post a comment:

Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.