Tony Finch's blog

Nearly 10 years ago I developed a neat function for converting a Gregorian date into a count of days since some epoch. There was nothing particularly new about it; I just tweaked the numbers until the formula was as simple as possible. I've re-used this code a fair number of times since then without re-examining it. This evening I worked out that it can be distilled even more.

The function adds together some expressions that count the number of days indicated by the three components of the date, plus a constant to set the epoch.

The number of normal days before the year y (full four digit year) is just y*365.

The number of leap days up to and including the year y is y/4-y/100+y/400. This is the usual "add a leap day in every fourth year, but not in every hundredth year, but do in every 400th year" rule. I'm using integer division that discards any remainder, i.e. rounds down.

The previous two paragraphs are inconsistent about including or excluding the current year. This is because leap days occur inside a leap year, not at the end, so their contribution to the day count does not depend solely on the year. We can fix this by re-assigning January and February to the previous year using a small administrative fiddle, as follows (where m counts months starting from 1). Then a leap day falls just before the start of years that are multiples of four (etc.) and the expression in the previous paragraph magically does the right thing. The fiddle also requires an adjustment to the epoch constant.

        if (m > 2) m -= 2; else m += 10, y -= 1;

Months are the part that I spent most time fiddling with. Section 1.12 of Calendrical Calculations develops various equations for calendars (such as the Julian calendar) that spread their leap years evenly, like Bresenham's line drawing algorithm spreads out raster steps. The equations also work for month lengths in the Julian and Gregorian calendars, if you treat 30-day months as normal years and 31 day months as leap years, and ignore February. We want to calculate the number of days in a year before the start of a given month, which is calculated by equation 1.73:

        (L*y - L + D*L % C) / C + (y - 1) * N

where L is the number of leap years in a cycle, C is the total number of years in a cycle, D is the offset of the start of the cycle, N is the number of days in a normal year, and years are actually months. Yuck. It turns out that if we perform the right administrative fiddling, we can arrange that D=0, and we can substitute m=y-1. This gives us the greatly simplified:

        m*L/C + m*N = m * (N*C+L) / C

For Julian and Gregorian months, N=30, C=12, and L=7, giving m*367/12. This pretends that February has 30 days, but the pretence doesn't matter because we have moved February to the end of the year so we never count days after February 28th or 29th . The complete function is then as follows (with the epoch set so that 1st January, 1 A.D. is day 1).

    int A(int y, int m, int d) {
        if (m > 2) m -= 2; else m += 10, y -= 1;
        return y*365 + y/4 - y/100 + y/400 + m*367/12 + d - 336;
    }

In fact you don't have to treat a whole year as a cycle for the purpose of the month calculation. The most basic pattern is a five month cycle containing three long months, as in March-July and August-December. (January and February are the start of a third truncated cycle.) However when I tried to make m*153/5 work in 1999 I could not eliminate the D offset to keep the equations simple. My problem was that I only allowed myself to count months starting from zero or one, and I was flailing around without the sage guidance of messrs. Dershowitz and Reingold. (I didn't use their equation 1.73 when I was developing this code, but it's a good example of what I was trying to avoid.)

It turns out that we can play around with the administrative fiddle to adjust D so that the cycle falls in the right place, so long as we compensate by adjusting the epoch constant. For the Julian and Gregorian five-month cycle D=4, i.e. we need to shift March (the start of the cycle) to month number 4, which gives us the following code.

    int B(int y, int m, int d) {
        if (m > 2) m += 1; else m += 13, y -= 1;
        return y*365 + y/4 - y/100 + y/400 + m*153/5 + d - 428;
    }

I mentioned above that equation 1.73 works for Julian leap years, so we can use it for years as well as months. This combines first two terms of the return expression leaving the Gregorian correction separate. No additional fiddling is necessary. We can't merge in the Gregorian correction as well, because evenly spreading the leap years gives intervals of 4 or 5, not 4 or 8.

    int C(int y, int m, int d) {
        if (m > 2) m += 1; else m += 13, y -= 1;
        return y*1461/4 - y/100 + y/400 + m*153/5 + d - 428;
    }

There's a related function for calculating the number of days in a month. It uses the remainders from the divisions to find the length of the current month, instead of using the results to count the preceding days. My old code re-used the same administrative fiddle:

    int D(int y, int m) {
        if (m > 2) m -= 2; else m += 10;
        return m*367%12 > 4 ? 31
             : m != 12     ? 30
             : y % 4      ? 28
             : y % 100   ? 29
             : y % 400  ? 28
                       : 29;
    }

In fact you don't need a fiddle in this case, because there's no need to move February to the end of the year. You can just pick values of C and L which make the pattern fall in the right place.

    int E(int y, int m) {
        return m*275%9 > 3 ? 31
             : m != 2     ? 30
             : y % 4     ? 28
             : y % 100  ? 29
             : y % 400 ? 28
                      : 29;
    }

Thanks for all the interesting comments on my previous post.

The reason I'm investigating this is to work around false positives caused by SpamAssassin's obfuscation rules. These are intended to match deliberate misspellings of commonly spammed goods such as Viagra. The specific instance that caused the bug report was a Reading postcode being treated as an obfuscated Rolex.

Therefore I'm not particularly worried about missing out obscure special cases like GIR 0AA and the overseas territories AAAA 1ZZ. However it might be worth tightening up the outcode regex, based on the list of UK postcode areas, to reduce the chance of matching a bogus postcode.

Also, the Post Office's postcode FAQ mentions that only London uses the ANA and AANA outcode formats. (In fact it's only the E, EC, SW, W, WC areas.) I managed to find a list of postcode districts which includes these outcodes (Wikipedia omits them) and it shows that the third position rule is wrong: it says M does not appear there but there is a poscode district London W1M. Rule Three also allows A and E which are not in fact used.

qr{\b
  ([BGLMNS][1-9][0-9]?
  |[A-PR-UWYZ][A-HK-Y][1-9]?[0-9]
  |([EW]C?|NW?|S[EW])[1-9][0-9A-HJKMNPR-Y]
  )[ ]{0,2}
  ([0-9][ABD-HJLNP-UW-Z]{2})
\b}x

I've now read Dan Kaminsky's slides, which are mostly ranting "the sky is falling" and pointing out what assumes secure DNS. The actual attack is not described in any more detail than previous public sources. I still don't understand why resolvers accept the poison: Kaminsky seems to be suggesting that data in the additional section of a reply is overwriting cached answers, which RFC 2181 says must not happen. Anyway,

$ md5 <kaminsky; echo; cat kaminsky; echo
ef96f2d9e973a36e825793ddeff48ae5

Kaminsky says his attack allows him to overwrite data in a DNS cache.
The reason Matasano's glue / additional RR explanation is wrong can be
found in RFC 2181 section 5.4.1, which says that additional RRs must
not override authoritative data in the DNS cache. However, if you look
at RFC 1034 section 3.6.2 you'll see that the data for a CNAME target
goes in the answer section, not the additional section. Presumably
this means the resolver treats it as trustworthy and therefore
overwrites its "old" cached data with the CNAME target data. (However
RFC 2181 also says that a resolver shouldn't trust CNAME target data,
which implies this attack shouldn't work, though I can see why it does
if the CNAME target is in the same zone as the CNAME owner.)

So the attack is: (1) cause the victim to look up lots of random
invalid domain names adjacent to the goal name whose data you want to
overwrite; (2) spoof authoritative answers that contain two records: a
CNAME whose owner is your random invalid name and whose target is your
goal name, plus the data for the goal name that you want to insert
into the victim's cache; (3) when you win the spoofing race your data
for the goal name overwrites whatever the victim previously had
cached.

$ md5 <kaminsky2; echo; cat kaminsky2
d4b70e6abfa3e7d49e159d75b5fc277b

So there's another form of attack which is closer to the Matasano
description but still different in significant ways. This relies on
the fact that (again according to RFC 2181 section 5.4.1) data in the
authority section of a reply is given a lot of trust. The attack is:
(1) cause the victim to look up lots of random invalid domain names
adjacent to the goal name whose data you want to overwrite; (2) spoof
authoritative answers that have an authority section containing
replacement NS records for the target's zone which point to
nameservers you control; (3) when you win the spoofing race the victim
will start using your name servers for the target zone instead of the
proper nameservers; (4) your nameserver can reply in whatever way you
want for the target name, but you'll have to wait for it to expire
from the victim's cache. Therefore this attack is slower than the
CNAME attack.

I have released a new version of selog. The only significant change is C++ support, requested by filecoreinuse.

One thing I would like to be able to do in C++ is call a selector, so that sel(fmt, ...) works like selog(sel, fmt, ...). (The Lua API supports something like this.) However as far as I can tell this would require variadic templates to implement efficiently (i.e. to inline the selog_on() check) and this is probably reaching too far into voodoo territory to be sensible.

So there's another form of attack which is closer to the Matasano description but still different in significant ways.

$ md5 <~/doc/kaminsky2
d4b70e6abfa3e7d49e159d75b5fc277b

I've just read a paper about "Foundation", which is an updated version of Plan 9's Venti archiving system. Foundation is designed to back up a computer nightly to a USB hard disk and an FTP server. Like Venti, it uses content-addressed storage to eliminate duplicate blocks; the main difference is that Foundation has been optimized to reduce seeks on a single disk, where Venti assumed a fast RAID could hide latency. Foundation uses a Bloom filter to speed up index lookups when eliminating duplicate blocks, and it writes data blocks in an append-only log, so it hits two things that I have been thinking about recently.

Towards the end of the paper are a few wonderful paragraphs that address the problem of reclaiming backup space wasted by bulky temporary data - the paper uses the example of on-disk copies of DVDs to save physical space when travelling. This motivates the desire to support deleting a nightly snapshot. They say:

Conceptually, deleting a snapshot resembles garbage collection in programming languages or log cleaning in LFS. First, the CAS layer writes a new version of the system catalog that no longer points to the snapshot. Then, the system reclaims the space used by blocks that are no longer reachable from any other catalog entry. A more recent snapshot, for example, may still point to some block in the deleted snapshot.

Interestingly, the structure of Foundation's log makes identifying unreferenced blocks particularly efficient: as a natural result of the log being append-only, all pointers within the log point "backwards". Garbage collection can thus proceed in a single, sequential pass through the log using an algorithm developed by Armstrong and Virding for garbage collecting immutable data structures in the Erlang programming language.

The algorithm works as follows. Starting at the most recent log entry and scanning backwards, it maintains a list of "live" blocks initialized from the pointers in the system catalog. Each time it encounters a live block, it deletes that block from its list. If the block is a metadata block that contains pointers to other blocks, it adds these pointers to its list. If the algorithm encounters a block that is not in its list, then there are no live pointers to that block later in the log, and since all pointers point backwards, the algorithm can reclaim the block's space immediately. The system can also use this algorithm incrementally: starting from the end of the log, it can scan backward until "enough" space has been reclaimed, and then stop.

The expensive part of the Erlang algorithm is maintaining the list of live blocks. If references to many blocks occur much later in the log than the blocks themselves, this list could grow too large to fit in memory. We note, however, that a conservative version of the collector could use a Bloom filter to store the list of live blocks. Although false positives in the filter would prevent the algorithm from reclaiming some legitimate garbage, its memory usage would be fixed at the size of the Bloom filter.

This reminds me of a recent post on Phil Wadler's blog where he highlights some comments on the proposal to add functional programming to the ACM curriculum. The paragraphs I quoted above are an excellent example of FP knowledge being useful in all parts of computer science.

There's been a raft of phishing attacks against Universities over the last few months. We received a couple of thousand of these last night:

Subject:  CONFIRM YOUR EMAIL ADDRESS
Date:     Tue, 6 May 2008 16:08:53 -0400
From:     CAM SUPPORT TEAM 
Reply-To: 

Dear Cam Subscriber,

To complete your (CAM) account, you must reply to this email
immediately and enter your password here (*********)

Failure to do this will immediately render your email address
deactivated from our database.

You can also confirm your email address by logging into your
CAM account at www.webmail.cam.ac.uk/

Thank you for using CAM.AC.UK!
FROM THE CAM SUPPORT TEAM

We did the usual announcement dance, including a notice on the webmail login page, but this did not prevent some users (including webmail users!) from replying to the phish.

captain_aj suggests scanning email to reject it if it contains the user's password. I wonder how long it would take to crypt() every word of every message... :-)

During a discussion on a work mailing list about TCP performance across the Atlantic, one of my colleagues made some comments that were ridiculous even by his standards. (He's notorious for declaring ex cathedra that things are extremely difficult and no-one understands them any more except a few giants (like himself) from the age when dinosaurs ruled the machine room.) I felt compelled to correct his most egregiously wrong statements, and I'm posting my comments here since they seem to be of wider interest than just University IT staff. In the quoted sections below, when he talks about "products" he means software that games or breaks TCP's fairness and congestion control algorithms.

I went to a very interesting talk by the only TCP/IP experts I have ever met who explained that the only reason the Internet works is that such products were NOT in widespread use.

The importance of congestion control has been common knowledge since the Internet's congestion collapse in the 1980s and Van Jacobson's subsequent TCP algorithm fixes. (It's taught to all CS undergrads, e.g. look at the Digital Communications 1 syllabus in CST part 1B.) However software that games TCP's fairness model *is* in widespread use: practically all P2P software uses multiple TCP connections to get better throughput.

In the mid 1990s the Internet was going to melt down because of all the web browsers making lots of connections that were too short for TCP's congestion control algorithms to be effective. So we got HTTP/1.1 with persistent connections and a limit on the concurrency that browsers use. However these TCP and HTTP measures only work because practically all software on end-hosts co-operates in congestion control: there's nothing to enforce this co-operation.

The rise of P2P means that ISPs are increasingly interested in enforcing limits on bandwidth hogs, hence the arguments about "network neutrality" as the ISPs point fingers at YouTube and the BBC and the file sharers. They are also deploying traffic shapers in the network which manipulate TCP streams with varying degrees of cleverness. (The most sophisticated manipulate the stream of ACKs going back to the sender which causes it to send at the network's desired rate; the stupid ones like Comcast's just kill connections they don't like.)

However, a better approach is to use a more realistic idea of fairness as the basis for congestion control instead of equal bandwidth per TCP connection. e.g. for ISPs, balance per subscriber. Bob Briscoe's recent position paper makes this argument in readable fashion. RFC 2140 groped in the same direction 10 years ago, but was never adopted. Either way, enforcement at the network's edge (instead of trusting the hosts) is likely to be the future whatever model of fairness is used.

Also interesting is the research on adapting TCP to high-bandwidth networks. There are many examples of what Briscoe argues against: great efforts of design and analysis to preserve TCP-style fairness in the new protocols. The GÉANT2 high-speed TCP page has lots of relevant links.

Luckily, there are very few people who know enough about TCP/IP and related protocols to write an effective product because, as I implied, there are probably no more than half-a-dozen TCP/IP experts in the world still working (and may even be none).

Tosh. There's a substantial market out there, both for managing congestion and for exploiting weaknesses in congestion control.

This has to be the strangest (or stupidest) way that I have seen of treating ports < 1024 specially.

It seems that the nameservers for spacely.net drop any queries that use a source port < 1024. (They also serve domains such as ChristopherReeve.org, which is a brain research funding charity and the reason I found out about the problem.) It was a complete bugger to diagnose, because dig of course uses a high source port, so it was able to resolve names without a problem. My nameservers (and chiark's) use the traditional source port 53, so they were in trouble. By default bind now uses high source ports so most sites would not trip over the stupidity.

I guess it's time to remove that bit of ancient paranoia from my usual named.conf options section.

; <<>> DiG 9.3.4 <<>> -b 131.111.8.132#1023 mx ChristopherReeve.org @ns.spacely.net
; (1 server found)
;; global options:  printcmd
;; connection timed out; no servers could be reached

; <<>> DiG 9.3.4 <<>> -b 131.111.8.132#1024 mx ChristopherReeve.org @ns.spacely.net
; (1 server found)
;; global options:  printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 5873
;; flags: qr aa rd ra; QUERY: 1, ANSWER: 2, AUTHORITY: 0, ADDITIONAL: 2

;; QUESTION SECTION:
;ChristopherReeve.org.          IN      MX

;; ANSWER SECTION:
ChristopherReeve.org.   14400   IN      MX      10 mail.ChristopherReeve.org.
ChristopherReeve.org.   14400   IN      MX      5 mail1.ChristopherReeve.org.

;; ADDITIONAL SECTION:
mail.ChristopherReeve.org. 14400 IN     A       66.215.16.66
mail1.ChristopherReeve.org. 14400 IN    A       67.151.7.145

;; Query time: 185 msec
;; SERVER: 64.209.141.253#53(64.209.141.253)
;; WHEN: Thu Apr 17 12:53:08 2008
;; MSG SIZE  rcvd: 113

• An active PS/2 to USB keyboard adaptor that doesn't work with my old :CueCat, so I can't use the :cc with my Mac.
• An old laptop PC with a flaky CDROM drive that refuses to read most OS install media, so I'm stuck with ancient FreeBSD and no wireless support until I can upgrade.
• The :cc's stupid habit of typing Alt+F10 before the encoded barcode data, which occasionally gives Mozilla the heebie-jeebies or even accidentally kills it.
• LibraryThing in overload mode refusing to let me log in again.

On the other hand, one of my old bug reports reminded me how to get a SHARP PC-AR10 working with FreeBSD-4.X without much trouble, and when LT deigns to let me log in its import features are really easy to use.

I'm pleased to announce the first release of selog, which you can download from <http://dotat.at/prog/selog/>.

Selog is a library of routines that unifies error reporting, activity logging, and debug tracing. It allows programmers to give their users flexible control over which messages are written and where they are written to.

Selog is designed to be as simple as possible while still being extremely efficient, powerful, and flexible. The essence of selog is:

• Obtain a configuration string from the user, which looks like:

  +log_pid+example@syslog;-example@stderr

• When the program starts, initialize selog with the user's configuration.

  selog_open(config, spelling)

• Define a selector for each different kind of message.

  static selog_selector sel = SELINIT("example", SELOG_INFO);

• Use the selog() function to emit messages instead of printf() or syslog().

  selog(sel, "message number %d", n);

Selectors determine which messages are written and where they are written to, under the control of the user's configuration. You can direct messages to any combination of stderr, syslog, files, pipes, etc. You can omit or include optional parts of messages under the control of selectors. You don't have to signal the program when you rotate its log files.

The C interface consists of just 13 functions, 5 macros, 2 types, and an enum. There are a few variations of the basic selog() one-shot logging function, or you can quickly and easily compose messages in stages. The check to skip disabled messages is extremely small and fast.

Selog comes with shell command and Lua interfaces, plus interposition libraries which you can use to fool old code that calls err() or syslog() into using selog instead.

Selog's origins

I started work on selog when I found myself writing yet another half-arsed logging/debugging module that could only be used by the program it was written for. The problem needed to be solved properly, but I couldn't find a decent existing solution.

Exim's logging and debugging facilities provided the basis for selog's configuration syntax and the idea for the fast check to disable debugging code. Like many other programs, Exim's logging and debugging code is non-orthogonal and non-reusable; selog exists to avoid problems like Exim's fixed set of log files and the lack of debugging redirection.

The architecture of log4j and its many imitators provided many nice ideas to copy, in particular selog's selectors and channels are similar to log4j's loggers and appenders. However log4j is unnecessarily complicated, so selog discards plenty of its ideas, such as hierarchial category names and arbitrarily configurable message layouts. Bloaty log4c provided a salutory anti-pattern.

I've tried to make this first release fairly polished - e.g. it has comprehensive documentation - however it has not had its portability catches polished off, and in particular I'm going to be interested to see how much trouble my use of C99 features causes. The next step is to go back to the program that I wrote selog for, and put the code to use...

The Game of Life is fairly pointless, but in this case it is also written in "point-free" style which minimizes the use of variables. I think it's quite cute.

It's easy to represent an unbounded quarter-plane in Haskell as [[Cell]], i.e. a list of rows of cells - the lists are lazy, so they can make themselves as long as necessary. You can then define the universe without form and void, such that darkness is upon the face of the screen, as:

  data Cell = Dead | Alive
  deadline = repeat Dead
  deadspace = repeat deadline

To create a pattern we add live cells to this substrate. First we need a helper function that changes just the Nth element of a list:

  mapNth n f xs = as ++ f b : cs
    where (as,b:cs) = splitAt n xs

Then to set an individual cell we use mapNth to modify the Xth element of the Yth row. Pointfree style tends to use the $ operator a lot, which makes Perl poetry-style programmers feel at home.

  setcell (x,y) = mapNth y $ mapNth x $ const Alive

We can apply setcell successively starting from dead space to create a pattern. For example, here's a glider set to run off into the unbounded corner of the universe.

  pattern = foldr setcell deadspace
  glider = pattern [(2,1),(3,2),(3,3),(2,3),(1,3)]

When working out the next generation we need to work out the neighbourhood of each cell, i.e. the 3x3 square consisting of the cell and its eight neighbours. We'll end up with the neighbourhood represented as a triple of triples, on which it's straightforward to specify the Game of Life rule:

  fromCell Dead = 0
  fromCell Alive = 1

  rule ((a,b,c),(d,e,f),(g,h,i)) =
      if count == 2 then e else
      if count == 3 then Alive else Dead
    where
      count = sum $ map fromCell [a,b,c,d,f,g,h,i]

The one-dimensional version of the neighbourhood is quite easy, turning a list into a list of overlapping triples.

  by3 (a:b:c:ds) = (a,b,c) : by3 (b:c:ds)
  by3     _      = []

We're going to apply by3 to each row to make horizontal triples, and to the list of rows itself to make triple rows of triples. However what we want is rows of triple triples. Turning a triple of lists into a list of triples is almost what zip3 does, except that zip3 is inconveniently curried.

  uncurry3 f (a,b,c) = f a b c
  zip3' = uncurry3 zip3

Then the code to turn a list of rows of cells into a list of rows of neighbourhoods is just as I outlined in the previous paragraph.

  by3by3 = map zip3' . by3 . map by3

When calculating the next generation, we want to add a strip of empty space to each edge of the universe, so that all our cells have neighbours. If we did not do this the universe would unravel at one cell per generation, a bit like in Greg Egan's book "Schildt's ladder".

  grow = (deadline:) . map (deadcell:)

Now we can actually calculate the next generation! Grow the universe, work out the neighbourhoods, then apply the rule to each of them.

  generate = map (map rule) . by3by3 . grow

To display the universe, we need to convert cells to strings

  instance Show Cell where
    show Dead = "  "
    show Alive = "[]"

To display the whole universe, we need to truncate it to the size of the screen by taking only the necessary elements from the lists, concatenate the string representation of the cells in each row, and join the rows with newlines.

  display (x,y) = unlines . map (concatMap show . take x) . take y

Then the main program simply loops displaying the universe and calculating its next generation.

  loop u = do
    putStrLn $ display (10,10) u
    _ <- getLine
    loop $ generate u

  main :: IO ()
  main = loop glider

Hashlife is a radically powerful way of computing Conway's Game of Life. It was invented by Bill Gosper who originally described it in his 1984 paper "Exploiting Regularities in Large Cellular Spaces", Physica D (Nonlinear Phenomena) volume 10 pp. 75-80.

Three weeks ago I wrote about Life In A Register which was a tangent from work I was doing on hashlife. I have not made much progress on it since then, so I thought I would post what I have done so far here, because it is the most interesting part. It's a literate-programming description of the algorithm, optimised for clarity of exposition, not speed. This post is (mostly) mechanically generated from the code I have written so far.

Hashlife uses several cunning techniques:

The universe is represented as a quadtree of nested squares that are powers of two cells on a side. There is an intricate and beautiful recursive function for computing life using this data structure.

It avoids constructing multiple copies of equivalent portions of the quadtree that are duplicated at different places or times by looking up previously-constructed squares in the eponymous hash table. (This technique is known as memoizing or hash-consing.) It also remembers the results of Life computations so that it does not need to repeat them.

Because of its aggressive memoization it is extremely effective at computing Life patterns that have some kind of repetition in space or time. Hashlife can take the same length of time to compute from generation N to generation 2N for any large enough N - it has logarithmic complexity. Its disadvantage is that it is not very fast at handling random Life soup.

There are a few hashlife resources on the web. There is David Bell's implementation, and Tomas Rokicki's implementation is part of the "Golly" Game of Life simulator. He also wrote about it for Dr Dobb's: "An Algorithm for Compressing Space and Time". For an example of hashlife's capabilities, it can compute 2^130 generations of the Metacatacryst producing a pattern of 2^232 cells. I first read about hashlife when working on my previous (more conventional) Life implementation.

First, a little bit of notation. Because hashlife can handle exceptionally large computations, we represent generation counts, population counts, display co-ordinates, etc. as multiprecision integers. Powers of two are particularly important, so because of the cost of creating mpz_t objects we pre-allocate a few of them. With any luck this upper bound will be overkill.

I'll also use this array for notation in the comments, so pow2[0] == 1, pow2[1] == 2, pow2[8] == 256, etc.

	#include <stdbool.h>
	#include <gmp.h>

	typedef unsigned char byte;

	#define LEVEL_MAX 1024

	static mpz_t pow2[LEVEL_MAX];

	static void
	init_pow2(void) {
		mpz_init_set_ui(pow2[0], 1);
		for(unsigned i = 1; i < LEVEL_MAX; i++) {
			mpz_init(pow2[i]);
			mpz_mul(pow2[i], pow2[i-1], pow2[i-1]);
		}
	}

Hashlife divides the universe up into a quadtree. A square at level N is pow2[N] cells on a side, and divided into four level N-1 quarters with half as many cells on a side, i.e. pow2[N-1]. We do not need to store the level explicitly since we can keep track of it by counting depth of recursion.

The code is written consistently to handle sub-squares in reading order named by compass points, as shown in this declaration. The quarter pointers are never NULL except in level 0 squares. The calc field can be NULL or a pointer to a level N-1 square; it is filled in lazily. We'll have much more to say about it below.

	typedef struct square {
		struct square *nw, *ne,
		              *sw, *se,
		              *calc;
		mpz_t *pop;
	} *square;

There are two level 0 squares, each being one cell that is live or dead. We don't represent this state explicitly, but instead just use the identities of the squares, so they don't need initialization. Read "sq_0" as "square level 0".

  sq_0[0]  sq_0[1]
    +  +     +  +
              ()
    +  +     +  +

	#define NUM_SQ_0 (1 << 1*1)

	static struct square sq_0[NUM_SQ_0];

This function returns 0 for a dead cell and 1 for a live cell. The pointer arithmetic is equivalent to (sq == &sq_0[1]).

	static inline bool
	alive(square sq) {
		return(sq - sq_0);
	}

The level 1 squares have a level 0 square (a cell) in each quarter, so they are 2*2 cells in size and have pow2[2*2] = 16 possible states. The state of each cell is represented by a pointer to sq_0[0] or sq_0[1].

	#define NUM_SQ_1 (1 << 2*2)

	static struct square sq_1[NUM_SQ_1];

	static void
	init_sq_1(void) {
		for(unsigned i = 0; i < NUM_SQ_1; i++) {
			unsigned nw, ne, sw, se;
			nw = (i & 1) >> 0;
			ne = (i & 2) >> 1;
			sw = (i & 4) >> 2;
			se = (i & 8) >> 3;
			square sq = &sq_1[i];
			sq->nw = &sq_0[nw];
			sq->ne = &sq_0[ne];
			sq->sw = &sq_0[sw];
			sq->se = &sq_0[se];
		}
	}

A level 2 square similarly comprises four level 1 squares, so it has 16 cells. Level 2 squares are interesting because they are the first squares that are big enough to calculate the next generation. We can calculate the next state of one of the four inner cells based on its eight surrounding cells as shown below:

   +--+--+--+--+    +--+--+--+--+    +--+--+--+--+    +--+--+--+--+
   |        |  |    |  |        |    |           |    |           |
   +  +--+  +  +    +  +  +--+  +    +--+--+--+  +    +  +--+--+--+
   |  |()|()|  |    |  |()|()|  |    |   () ()|  |    |  |() ()   |
   +  +--+  +  +    +  +  +--+  +    +  +--+  +  +    +  +  +--+  +
   |   () ()|  |    |  |() ()   |    |  |()|()|  |    |  |()|()|  |
   +--+--+--+  +    +  +--+--+--+    +  +--+  +  +    +  +  +--+  +
   |           |    |           |    |        |  |    |  |        |
   +--+--+--+--+    +--+--+--+--+    +--+--+--+--+    +--+--+--+--+

The state of a cell in the next generation is determined by its current state and the number of live neighbours.

	static bool
	life_rule(square nw, square nn, square ne,
	          square ww, square cc, square ee,
	          square sw, square ss, square se) {
		unsigned count;
		count = alive(nw) + alive(nn) + alive(ne)
		      + alive(ww)             + alive(ee)
		      + alive(sw) + alive(ss) + alive(se);
		return(count == 2 ? alive(cc) : count == 3);
	}

However we do not have enough information to calculate the next states of the outer cells because our focus is currently too narrow to see how the surrounding pattern might affect them.

   +--+--+--+--+--+
   |     |     |??|
   +  +  +  +--+  +
   |   ()|()|  |??|
   +  +  +  +--+  +
   |   ()|()   |??|
   +  +  +--+--+--+
   |           |
   +--+--+--+--+

All we can say, given a level 2 square, is that we can compute the state after one generation of a level 1 square aligned to the same centre. We will see in a moment how to use this as the basis for calculating the futures of bigger squares.

We pre-compute the result of the calculation on level 2 squares and store it in the square's calc field for re-use later. In larger squares this field is only filled in when necessary, but in the level 2 case it is always filled in so that it acts as a sentinel to save us from explicitly testing for the base case of the recursion.

For reference when reading the double dereferencing, here's a diagram of how the constituent level 1 sub-squares and level 0 sub-sub-squares within a level 2 square are laid out.

     +--+--+--+--+
     |nw ne|nw ne|
  nw +  +  +  +  + ne
     |sw se|sw se|
     +--+--+--+--+
     |nw ne|nw ne|
  sw +  +  +  +  + se
     |sw se|sw se|
     +--+--+--+--+

	#define NUM_SQ_2 (1 << 4*4)

	static struct square sq_2[NUM_SQ_2];

	static void
	init_sq_2(void) {
		for(unsigned i = 0; i < NUM_SQ_2; i++) {
			unsigned nw, ne, sw, se;
			nw = (i & 0x000F) >> 0;
			ne = (i & 0x00F0) >> 4;
			sw = (i & 0x0F00) >> 8;
			se = (i & 0xF000) >> 12;
			square sq = &sq_2[i];
			sq->nw = &sq_1[nw];
			sq->ne = &sq_1[ne];
			sq->sw = &sq_1[sw];
			sq->se = &sq_1[se];
			// Calculate Life on the four possible 3x3 groups:
			unsigned calc = 0;
			calc |= life_rule(sq->nw->nw, sq->nw->ne, sq->ne->nw,
			                  sq->nw->sw, sq->nw->se, sq->ne->sw,
			                  sq->sw->nw, sq->sw->ne, sq->se->nw) << 0;
			calc |= life_rule(sq->nw->ne, sq->ne->nw, sq->ne->ne,
			                  sq->nw->se, sq->ne->sw, sq->ne->se,
			                  sq->sw->ne, sq->se->nw, sq->se->ne) << 1;
			calc |= life_rule(sq->nw->sw, sq->nw->se, sq->ne->sw,
			                  sq->sw->nw, sq->sw->ne, sq->se->nw,
			                  sq->sw->sw, sq->sw->se, sq->se->sw) << 2;
			calc |= life_rule(sq->nw->se, sq->ne->sw, sq->ne->se,
			                  sq->sw->ne, sq->se->nw, sq->se->ne,
			                  sq->sw->se, sq->se->sw, sq->se->se) << 3;
			sq->calc = &sq_1[calc];
		}
	}

Given the pre-calculated results for level 2 squares, how can use them to calculate the next generation of a level 3 square? We can't just recurse on its four quarters because that leaves gaps between the results:

   +--+--+--+--+--+--+--+--+
   |                       |
   +  +--+--+  +  +--+--+  +
   |  |     |     |     |  |
   +  +  +  +  +  +  +  +  +
   |  |     |     |     |  |
   +  +--+--+  +  +--+--+  +
   |                       |
   +  +  +  +  +  +  +  +  +
   |                       |
   +  +--+--+  +  +--+--+  +
   |  |     |     |     |  |
   +  +  +  +  +  +  +  +  +
   |  |     |     |     |  |
   +  +--+--+  +  +--+--+  +
   |                       |
   +--+--+--+--+--+--+--+--+

To solve this problem the level 2 sub-squares need to overlap so that their smaller level 1 results abut. We achieve this by re- arranging the level 1 sub-sub-squares to make five extra level 2 sub-squares. We then have a total of nine overlapping level 2 squares. (These diagrams are half-size.)

   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+
   |     |     |   |  |     |  |   |     |     |
   +  +  +  +  +   +  +  +  +  +   +  +  +  +  +
   |   nw|     |   |  |  n  |  |   |     |ne   |
   +--+--+  +  +   +  +--+--+  +   +  +  +--+--+
   |           |   |           |   |           |
   +  +  +  +  +   +  +  +  +  +   +  +  +  +  +
   |           |   |           |   |           |
   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+

   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+
   |           |   |           |   |           |
   +--+--+  +  +   +  +--+--+  +   +  +  +--+--+
   |     |     |   |  |     |  |   |     |     |
   +  + w+  +  +   +  +  c  +  +   +  +  +e +  +
   |     |     |   |  |     |  |   |     |     |
   +--+--+  +  +   +  +--+--+  +   +  +  +--+--+
   |           |   |           |   |           |
   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+

   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+
   |           |   |           |   |           |
   +  +  +  +  +   +  +  +  +  +   +  +  +  +  +
   |           |   |           |   |           |
   +--+--+  +  +   +  +--+--+  +   +  +  +--+--+
   |   sw|     |   |  |  s  |  |   |     |se   |
   +  +  +  +  +   +  +  +  +  +   +  +  +  +  +
   |     |     |   |  |     |  |   |     |     |
   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+

We're going to need these nine sub-squares in a couple of places so let us define helper functions for finding them. The main find() function (which I have not written yet) looks up a square in the hash table based on its four constituent sub-squares, or constructs a new square if it was not found. For reference, here's the sub+subsub diagram again.

     +--+--+--+--+
     |nw ne|nw ne|
  nw +  +  +  +  + ne
     |sw se|sw se|
     +--+--+--+--+
     |nw ne|nw ne|
  sw +  +  +  +  + se
     |sw se|sw se|
     +--+--+--+--+

	static square find(square nw, square ne, square sw, square se);

	static inline square find_nw(square sq) {
		return(sq->nw);
	}
	static inline square find_nn(square sq) {
		return(find(sq->nw->ne, sq->ne->nw,
		            sq->nw->se, sq->ne->sw));
	}
	static inline square find_ne(square sq) {
		return(sq->ne);
	}
	static inline square find_ww(square sq) {
		return(find(sq->nw->sw, sq->nw->se,
		            sq->sw->nw, sq->sw->ne));
	}
	static inline square find_cc(square sq) {
		return(find(sq->nw->se, sq->ne->sw,
		            sq->sw->ne, sq->se->nw));
	}
	static inline square find_ee(square sq) {
		return(find(sq->ne->sw, sq->ne->se,
		            sq->se->nw, sq->se->ne));
	}
	static inline square find_sw(square sq) {
		return(sq->sw);
	}
	static inline square find_ss(square sq) {
		return(find(sq->sw->ne, sq->se->nw,
		            sq->sw->se, sq->se->sw));
	}
	static inline square find_se(square sq) {
		return(sq->se);
	}

When we calculate the next generation of each of these nine overlapping level 2 sub-squares, we get nine abutting level 1 squares like this:

   +--+--+--+--+--+--+--+--+
   |                       |
   +  +--+--+--+--+--+--+  +
   |  |     |     |     |  |
   +  + n w + n n + n e +  +
   |  |     |     |     |  |
   +  +--+--+--+--+--+--+  +
   |  |     |     |     |  |
   +  + w w + c c + e e +  +
   |  |     |     |     |  |
   +  +--+--+--+--+--+--+  +
   |  |     |     |     |  |
   +  + s w + s s + s e +  +
   |  |     |     |     |  |
   +  +--+--+--+--+--+--+  +
   |                       |
   +--+--+--+--+--+--+--+--+

We can calculate a second generation by combining these into four overlapping level 2 squares and then working out their results. This gives us four abutting level 1 squares as follows. I have labelled each of these new level 1 squares with the four previous level 1 squares that were used to make their parent level 2 squares. The repeated labels indicate where the overlap occurs.

   +--+--+--+--+--+--+--+--+
   |                       |
   +  +  +  +  +  +  +  +  +
   |                       |
   +  +  +--+--+--+--+  +  +
   |     |nw nn|nn ne|     |
   +  +  +  +  +  +  +  +  +
   |     |ww cc|cc ee|     |
   +  +  +--+--+--+--+  +  +
   |     |ww cc|cc ee|     |
   +  +  +  +  +  +  +  +  +
   |     |sw ss|ss se|     |
   +  +  +--+--+--+--+  +  +
   |                       |
   +  +  +  +  +  +  +  +  +
   |                       |
   +--+--+--+--+--+--+--+--+

Finally we combine these level 1 squares to make another level 2 square. We could use this to calculate a third generation, but we do not because after two generations the work we have done starting from a level 3 square is twice as big in every dimension - both space and time - as the level 2 calculation. This gives us a perfect recursive structure, which is the key to the algorithm.

                level 2  level 3  level N
   input size    4 * 4    8 * 8   pow2[N] * pow2[N]
   output size   2 * 2    4 * 4   pow2[N-1]*pow2[N-1]
   generations     1        2     pow2[N-2]

In Life, the "speed of light", the maximum speed that a signal can propagate, is one cell per generation. This is the rate at which the behaviour of surrounding squares can affect more and more of the cells around the edge of our current square as time passes. Eventually after pow2[N-2] generations our focus is too narrow to say anything about a border pow2[N-2] cells wide, and we only know about the middle square pow2[N-1] cells across. (This is why a square's calc field points to a level N-1 square, just like its quarter fields.) Hence, the ziggurat (truncated pyramid) shape formed by hashlife's recursion is the "past light cone" of the result square, that is, it includes all the cells in past generations that can possibly affect the state of the cells in the result.

The calculation function itself is memoized, i.e. it avoids repeating work by storing its result in the square. This makes the overlapping recursive structure feasible, because without the memoization it would lead to enormous amounts of recomputation. Another way of looking at this is lazy evaluation of the calc field, i.e. call-by-need, where we explicitly force evaluation of the calc field by calling calc2(). The combination of maximal sharing of equivalent squares (enabled by find()'s hash table), memoization of results, and divide-and-conquer recursion is what gives hashlife its amazingly fast logarithmic complexity for patterns that have repeating behaviour.

The memoization is where the pre-computed level 2 calc results act as sentinels, since the test for a memoized result always succeeds at level 2 and terminates the recursion.

	static square
	calc2(square sq) {
		// Check for a memo or a sentinel.
		if(sq->calc)
			return(sq->calc);
		// Find level N-1 sub-squares and calculate level N-2 results.
		square
		    nw = find_nw(sq), nn = find_nn(sq), ne = find_ne(sq),
		    ww = find_ww(sq), cc = find_cc(sq), ee = find_ee(sq),
		    sw = find_sw(sq), ss = find_ss(sq), se = find_se(sq);
		nw = calc2(nw); nn = calc2(nn); ne = calc2(ne);
		ww = calc2(ww); cc = calc2(cc); ee = calc2(ee);
		sw = calc2(sw); ss = calc2(ss); se = calc2(se);
		// Construct intermediate overlapping level N-1 squares
		// and calculate their level N-2 results.
		nw = calc2(find(nw, nn, ww, cc));
		ne = calc2(find(nn, ne, cc, ee));
		sw = calc2(find(ww, cc, sw, ss));
		se = calc2(find(cc, ee, ss, se));
		// Memoize the result.
		sq->calc = find(nw, ne, sw, se);
		return(sq->calc);
	}

What if we want to calculate a number of generations that isn't a power of two? We keep exactly the same spatial geometry (relative sizes and positions of input and output squares) as for the full calculation, so that the recursion also has the same shape. The simplest case of calculating fewer generations is zero, in which case we just construct a sub-square centred on the original square. In fact we already have code to do this in find_cc().

In the more general case the desired generation count is between 0 as worked out by find_cc(), and pow2[N-2] as worked out by calc2(). There are three kinds of recursion depending on whether the target falls before, on, or after the midway generation pow2[N-3]. This point in time corresponds to the age of the nine intermediate results in calc2(), which is also a dividing point in its code and in calc1() below.

                    recursion in first part or second part
           0 < gen < pow2[N-3]      calc1        find_cc
               gen = pow2[N-3]      calc2        find_cc
   pow2[N-3] < gen < pow2[N-2]      calc2         calc1

In calc1() we test the type of recursion for each part separately, and the three cases arise from the way the two tests overlap when cmp == 0. In the second part we have to adjust the generation count so that it is relative to the midway point, and we must restore its value before returning so that it appears unchanged to the caller. (We manipulate its value in-place because that is more efficient than allocating and freeing a local mpz_t with the required value.)

The following code assumes that 0 < gen < pow2[N-2]. Again the base case of the recursion is not explicit. The level argument must not be less than 3, in which case the assumption implies that gen must be 1 which is equal to the halfway point. Therefore no more recursion via calc1() occurs, and the calls to calc2() return immediately because of the level 2 sentinels.

This function is not memoized, but instead relies on calc2() for efficiency.

	static square
	calc1(square sq, unsigned level, mpz_t gen) {
		// Number of generations to the midway point.
		mpz_t *half = &pow2[level - 3];
		int cmp = mpz_cmp(gen, *half);
		level -= 1;
		square
		    nw = find_nw(sq), nn = find_nn(sq), ne = find_ne(sq),
		    ww = find_ww(sq), cc = find_cc(sq), ee = find_ee(sq),
		    sw = find_sw(sq), ss = find_ss(sq), se = find_se(sq);
		if(cmp < 0) {
			nw = calc1(nw, level, gen);
			nn = calc1(nn, level, gen);
			ne = calc1(ne, level, gen);
			ww = calc1(ww, level, gen);
			cc = calc1(cc, level, gen);
			ee = calc1(ee, level, gen);
			sw = calc1(sw, level, gen);
			ss = calc1(ss, level, gen);
			se = calc1(se, level, gen);
		} else {
			nw = calc2(nw); nn = calc2(nn); ne = calc2(ne);
			ww = calc2(ww); cc = calc2(cc); ee = calc2(ee);
			sw = calc2(sw); ss = calc2(ss); se = calc2(se);
		}
		if(cmp > 0) {
			mpz_sub(gen, gen, *half);
			nw = calc1(find(nw, nn, ww, cc), level, gen);
			ne = calc1(find(nn, ne, cc, ee), level, gen);
			sw = calc1(find(ww, cc, sw, ss), level, gen);
			se = calc1(find(cc, ee, ss, se), level, gen);
			mpz_add(gen, gen, *half);
		} else {

In the following code, if we followed the pattern and called find_cc() where the code above calls calc1(), it would require up to eight allocations. We can reduce this maximum to just four by avoiding the creation of the intermediate results, and instead directly creating the results that find_cc() would return according to the following diagram.

   +--+--+--+--+--+--+
   |nw   |  n  |   ne|
   +  +--+--+--+--+  +
   |  |se sw|se sw|  |
   +--+  +  +  +  +--+
   |  |ne nw|ne nw|  |
   +ww+--+- c -+--+ee+
   |  |se sw|se sw|  |
   +--+  +  +  +  +--+
   |  |ne nw|ne nw|  |
   +  +--+--+--+--+  +
   |sw   |  s  |   se|
   +--+--+--+--+--+--+

			nw = find(nw->se, nn->sw, ww->ne, cc->nw);
			ne = find(nn->se, ne->sw, cc->ne, ee->nw);
			sw = find(ww->se, cc->sw, sw->ne, ss->nw);
			se = find(cc->se, ee->sw, ss->ne, se->nw);
		}
		return(find(nw, ne, sw, se));
	}

The code above is the essence of hashlife. The most important thing it omits is the definition of the find() function, which serves as the square constructor. It has to implement hash-consing, i.e. it only ever constructs one copy of a square with a given set of arguments, to ensure maximal sharing. For serious use it must also implement garbage collection. I don't know if I can leave that job to the Boehm-Demers-Weiser conservative collector, but if I do then I'll have to do something cunning with weak pointers in find()'s hash table.

Maybe I'll write that eventually...

This is in response to mathew's recent post. I'm posting it here (and emailing it) because I can't get his frustrating Wordpress installation to log me in.

He asks, "It’s possible to write some C code to work out whether a machine’s architecture is little-endian or big-endian with respect to bytes. Is it possible, using only ANSI C, to work out whether the machine’s architecture is big-endian or little-endian with respect to bits?"

Machines do not (in general) have any bitwise endianness that's visible to programmers. In order to access bits you have to use shift and mask operations in registers, and these operations do not imply an absolute numbering of bits in the same way that the machine's addressing architecture does for bytes. (Instruction architecture documentation will often number the bits in a word, but a program running on the machine can't tell whether this documentation uses big-endian or little-endian conventions, or whether it numbers the bits from zero or one.)

Machines do have bitwise endiannes at a lower level that is invisible to the programmer, when buses or IO serialise and deserialise bytes, e.g. to and from RAM or disk or network. The serialized form is not accessible, so its endianness doesn't matter. There is an exception to this, which is output devices where the serialised form is visible to the user, e.g. displays with sub-byte pixels. But this is the device's endianness, not the whole machine's, and different devices attached to the same machine can legitimately disagree.

The same arguments about machines' instruction architectures apply to most of the C programming model, i.e. bits are mostly only accessible by shifts and masks, so endianness isn't visible. The exception is bit fields in structs, which allow words to be broken down into units of arbitrary size. Bit fields must have an endianness convention for how they are packed into words, but this is chosen by the compiler and need not agree with the hardware's byte-wise endianness. However the compiler usually does agree with the hardware, so that the following two structures have the same layout, though this is not required by the standard:

        struct a {
                unsigned char first;
                unsigned char second;
        };
        struct b {
                unsigned first : 8;
                unsigned second : 8;
        };

While writing up my notes on Bloom filters, I wanted a better idea of the relationship between the false positive rate and the size multiplier.

sm	= size / pop
pz	= exp(−nh ∗ pop / size)
	= exp(−nh / sm)
fpr	= (1 − pz) nh

Given a fixed number of hash functions, what size multiplier do we need to make enough space in the Bloom filter to produce the desired false positive rate? How does the size multiplier change as nh and fpr change? I wrote a program to solve this numerically, and the output is below. The entries for higher fprs show quite nicely that there's an optimal nh for a given fpr.

Try learning about SpamAssassin's notfirsthop DNS blacklist option, and why it might be a sensible idea, you utter cretins.

 This message was created automatically by mail delivery software.

 A message that you sent could not be delivered to one or more of its
 recipients. This is a permanent error. The following address(es) failed:

 zzzzzzzz@pts.edu
   SMTP error from remote mail server after end of data:
   host smtp.pts.edu [72.22.0.101]:
   554 Service unavailable; Client host [ppsw-5.csi.cam.ac.uk]
       blocked using Barracuda Reputation;
       http://bbl.barracudacentral.com/q.cgi?ip=86.165.170.59

 ------ This is a copy of the message, including all the headers. ------

 Return-path: <zzz99@cam.ac.uk>
 X-Cam-SpamDetails: Not scanned
 X-Cam-AntiVirus: No virus found
 X-Cam-ScannerInfo: http://www.cam.ac.uk/cs/email/scanner/
 Received: from [86.165.170.59] (port=51166 helo=[192.168.1.2])
           by ppsw-5.csi.cam.ac.uk (smtp.hermes.cam.ac.uk [131.111.8.155]:587)
           with esmtpsa (PLAIN:zzz99) (TLSv1:AES128-SHA:128)
           id 1JHf30-0003CD-Il (Exim 4.67)
           (return-path <zzz99@cam.ac.uk>); Wed, 23 Jan 2008 12:49:42 +0000
 Mime-Version: 1.0 (Apple Message framework v752.3)
 Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
 ...

The following C type definition can be used for declaring local and global structure objects. You can initialize them as if they were bare structures, because C doesn't mind if you omit curly brackets in initializers (though gcc -Wall will complain). You can also use the typedef to declare function arguments, in which case the function will expect a pointer to the structure instead of a copy of it. Furthermore, when you use a variable declared with this typedef, it will be quietly converted into a pointer to the structure just as is expected by the function. This avoids a load of & operators and gives you a sort of poor-man's C++ pass-by-reference.

        typedef struct mytype {
                /* member declarations */
        } mytype[1];

        mytype var;

        int func(mytype arg);

        func(var);

ETA: it seems this trick is used by GMP (see the last paragraph of that page)

Network Working Group                                         C. Hutzler
Request for Comments: 5068
BCP: 134                                                      D. Crocker
Category: Best Current Practice              Brandenburg InternetWorking
                                                              P. Resnick
                                                   QUALCOMM Incorporated
                                                               E. Allman
                                                          Sendmail, Inc.
                                                                T. Finch
                               University of Cambridge Computing Service
                                                           November 2007

  Email Submission Operations: Access and Accountability Requirements

Status of This Memo

   This document specifies an Internet Best Current Practices for the
   Internet Community, and requests discussion and suggestions for
   improvements.  Distribution of this memo is unlimited.

Abstract

   Email has become a popular distribution service for a variety of
   socially unacceptable, mass-effect purposes.  The most obvious ones
   include spam and worms.  This note recommends conventions for the
   operation of email submission and transport services between
   independent operators, such as enterprises and Internet Service
   Providers.  Its goal is to improve lines of accountability for
   controlling abusive uses of the Internet mail service.  To this end,
   this document offers recommendations for constructive operational
   policies between independent operators of email submission and
   transmission services.

   Email authentication technologies are aimed at providing assurances
   and traceability between internetworked networks.  In many email
   services, the weakest link in the chain of assurances is initial
   submission of a message.  This document offers recommendations for
   constructive operational policies for this first step of email
   sending, the submission (or posting) of email into the transmission
   network.  Relaying and delivery entail policies that occur subsequent
   to submission and are outside the scope of this document.