12

I'm working through a problem in Programming Pearls -- specifically, the implementation of a program which sorts a file containing, at most, 10,000,000 integers (Column 1, Problem 3). Since the book doesn't specify how the data should be stored in the file, I'm considering storing the integers as raw bytes (there are some other constraints that make raw bytes a good option). I've never worked at this low of a level before, so I want to know if there's anything dangerous I should watch out for. Do I need to worry about accidentally using some sort of end-of-file sequence when I'm writing raw bytes to a file, for example?

Edit:

I realize now how broad my question was. I really meant problems of the more catastrophic kind, like accidentally overwriting other files on the disk. Sorry I wasn't clearer originally.

Drake Sobania
  • 301
  • 2
  • 9
  • 6
    Note that Programming Pearls is a very old book; you could easily read the entire 10^7 integers into memory on a modern desktop machine, do the sort, and write it again. To get the original point of that chapter, limit the amount that you read at any time to a fraction of the total number. Or, increase the file size to around 10^10 integers. – Caleb Aug 27 '14 at 18:44
  • 3
    Actually, when I hear the word "dangerous", I think of things which make my PC explode, delete my bank accounts or something like that. And I guess it's most probably safe to assume that - as long as your program is not used for controlling an Airbus or a power plant - nothing really "dangerous" will happen when you try out what you have in mind. – Doc Brown Aug 27 '14 at 19:28
  • 4
    [There is no EOF character/sequence](http://latedev.wordpress.com/2012/12/04/all-about-eof/). –  Aug 27 '14 at 20:14
  • 2
    @delnan Years ago, when the myth of the EOF character was in vogue, I recall copy protection systems that were based on 'copy up to the EOF character' that many copy programs of the time did. Some programs would put additional data that they would check for *after* the EOF marker of an associated text file, but before the allocated end of the file. The copy program wouldn't copy the extra data validating a clean install... ahh... nostalgia. –  Aug 27 '14 at 20:23
  • danger? Like in "will my computer blow up if I do this"? Nope. – jwenting Aug 28 '14 at 06:37
  • Your biggest worry should be that the file might be unreadable on a different system if you don't take care of how many bytes there are in an integer and in which order they go (also called endianness). – Bart van Ingen Schenau Aug 28 '14 at 06:57
  • @Caleb even 10^10 integers can be easily mapped into 48-bit virtual space (though with memory mapped files there is danger of writing beyond end of file) and 40 GiB of memory including swap is not necessarily unheard of even on laptops (assuming 4 bytes per integer). If you want to make sure no cheats with in-place sort are done you need ~140 TiB of data. – Maciej Piechotka Aug 28 '14 at 08:38

4 Answers4

27

No, in fact this is how many file formats work. Common examples of binary files like this include images and music/audio files.

To maintain the integrity of the file and the data read from it, be sure to follow these guidelines:

  • Always open the file (reading or writing) using the same mode: text or binary. The primary difference is text mode cares about newlines, and may "chomp" off the newlines characters when reading a file (depending on the specific library being used). Text mode may also perform Unicode translations that will likely choke on non-Unicode data.
  • When reading non-string data, be sure to read using the same data type as you write. For example, if the first four bytes of the file are a descriptive integer, be sure to read and write using a method that takes/provides an integer to ensure it is treated consistently. The same data type may have a different size on different machines, and mixing data types on the same machine can also change the meaning of the data (e.g. interpreting a bit in the middle of a longer integer as a sign bit).
  • Endianness: if the library you are using does not handle this consistently, you may need to handle it yourself. For example, Java always uses network byte order (big endian) for multi-byte types. C and C++ use whatever the library implementer decided, typically the same as the processor (little endian on Intel, big endian on most others). If this is a quick exercise on one system it is not as important, but it is still a good habit to pay attention to this and code around it if necessary.

The specific details will vary based on the framework, platform, and language, but this should cover the basic "gotchas" with file I/O.

  • 3
    An additional point for non-string data: make sure that you use a consistent number of bytes for each type. In C and C++ an `int` can be anywhere between 2 and 8 or more bytes (octets really). – Bart van Ingen Schenau Aug 28 '14 at 07:00
  • That is implicitly included with my second point, e.g. 32 v. 64 bit integer. They would be different data types. –  Aug 28 '14 at 19:28
  • You might want to make it explicit. It isn't obvious that `int` on two different machines might be considered different datatypes. – Bart van Ingen Schenau Aug 29 '14 at 04:21
11

The only danger you will run into is little vs. big endianess (whether the most or least significant byte is written first). However if you remain in the same environment there will be no issue. besides the general ensuring of writing/parsing roundtrip.

The file system is designed to handle any sequence of bytes.

ratchet freak
  • 25,706
  • 2
  • 62
  • 97
  • 2
    +1 for the last line. I'm not sure the big/little issue is the *only* problem -- the OP could for example get confused about where the boundaries between integers is. But good answer anyway. – Caleb Aug 27 '14 at 17:56
9

In addition to all of the gotchas already mentioned, if you are making up a new binary file format rather than reading and writing data in an existing format, it is absolutely vital that you include a file header: a block of data at the very beginning of the file that unambiguously identifies the file format and records any metadata that may be required.

Good file headers include at least three things:

  • A "magic number", of at least four bytes. The magic number MUSTrfc2119 be the very first N bytes in the file, MUST never have been used for any other file format you can dig up, and MUST contain at least one byte that is not a printable ASCII character. See the PNG specification for how to design a really thorough magic number. See the source code of the file(1) command for a database of existing magic numbers that's as comprehensive as you're likely to find.

    The point of a magic number is to unambiguously label the file, in-band, with its format. If you don't include a magic number, or it's not the very first thing in the file, you run the risk of programs misidentifying your file as some other type of file, which leads to data loss, viruses escaping detection, and other such catastrophes.

  • An indication of the version of the file format. Even if you think you're never going to have to revise your file format drastically, make the next two bytes after the magic number be 00 00 and document that this is a 16-bit version number in some definite endianness (whichever you like, but pick one and stick to it throughout the file) and will be incremented if the meaning of subsequent data changes radically. Your future self will thank you.

    (The PNG specification takes a different route here, specifying that chunk formats are frozen, and that all future changes to the format will take the form of new chunk types. That's also valid, but I recommend the simple magic number+version number approach for beginners to binary data processing. The people who designed PNG were drawing on collective decades of experience with image formats.)

  • Some kind of mechanism for embedding arbitrary metadata in the file. This can be as simple as having the next two bytes be a 16-bit offset from the end of the header to the beginning of the actual data, with everything in between to be interpreted as UTF-8 key-value pairs a la RFC 822 (that is, "Tag: value\n" — if you go this route I recommend not allowing folding of long lines). Again, PNG is considerably cleverer.

zwol
  • 2,576
  • 1
  • 16
  • 16
  • No need to make up your own file format ... just store the data as an image. You might need to change the dimensionality (eg, 10k x 1k) so it'll be supported. Or you could use [FITS](http://fits.gsfc.nasa.gov/). If your data's more complex than just a single array, you could use [HDF](http://www.hdfgroup.org/HDF5/), [CDF](http://cdf.gsfc.nasa.gov/) or [NetCDF](http://www.unidata.ucar.edu/software/netcdf/). – Joe Aug 28 '14 at 13:25
  • I'd suggest to keep it simple. 256 different versions will suffice and if not, additional versions can be devised as subversions of version 255. Similarly for metadata, it's enough to add them in a the version when they're actually needed. @Joe Image??? You're avoiding the potential format confusion by confusing everyone beforehand! – maaartinus Aug 29 '14 at 16:23
  • @maaartinus Making the version field two bytes forces the format designer to commit to an endianness up front. Space for metadata should always be in version 0 of a binary format, otherwise you wind up with horrible kludges like ID3. I do have a great deal of sympathy for the PNG spec's logic regarding extensibility via new chunk types instead of format version bumps. However, chunk-structured files bring a bunch of complexity of their own so I hesitate to recommend them for simple cases. I *was* tempted to recommend HDF as a generic format that's dealt with lots of these issues already. – zwol Aug 29 '14 at 16:57
2

Different architectures have different representations for integers. The main risk here is saving the byte representation of an integer in machine A and then attempting to read that back and interpret the contents as integers in machine B. If machines A and B have different sizes for integers and/or different endianness, you'll most likely cause undefined behavior (e.g. in C) or an exception.

Since this is just a programming example and not a "real" program, it's not really an issue. If this were a real program, rolling your own application-specific binary format is usually not a good idea; there are better solutions, like SQLite or string-based serialization formats like JSON, YAML, XML, etc. For single values turning it into a string would suffice; for simple lists you could save one string per line and simply split the input on newlines when you read it back in.

Doval
  • 15,347
  • 3
  • 43
  • 58
  • Agree in general, but JSON or XML would significantly increase the size of a file containing 10^7 numbers. Also, they're generally read and parsed all at once, but the chapter in question deals with sorting files containing more data than you can fit in available memory. – Caleb Aug 27 '14 at 18:48
  • It depends on what you're doing. Sometimes the performance hit of SQL vs a roll-your-own is major. The last time I did it I had small records and there was a high chance I would want neighbors. Reading a bigger block off the disk would generally cost almost nothing so if I wanted one record I read 1000 into a cache. My records were almost certainly next to each other, with SQL the disk head would be bouncing all over the place. – Loren Pechtel Aug 28 '14 at 03:56