Notes on optimizing an O(n)+C algorithm where the C matters quite a bit

Monday, March 13, 2023

[Note: all hexadecimal values are preceeded with a “$”, which is old-school. I know these days it's hip to use “0x” to designate a hexadecimal value, but I hope this is just a passing fad. Also, the “K” here stands for “kilobyte,” which is 1024 bytes. This too, is old fasioned but I don't want to use a word that sounds like pet food. Geeze, kids these days!] [Here's an onion—put it on your belt, you geezer! —The kids] [Hey! I resemble that remark! Get off my lawn! —Sean]

I was doing a bit of retro computing over the weekend, writing 6809 code and running it on a Color Computer emulator (because the Color Computer was my first computer and the 6809 is a criminially underrated 8-bit CPU in my opinion). Part of the coding was enabling all 64K of RAM in the machine. Normally, the Color Computer only sees the lower 32K of RAM, with the upper 32K being ROM (the BASIC interpreter). To enable all 64K of RAM, all that's needed is to stuff any value into memory location $FFDF, which can be done with “POKE &HFFDF,0”. The problem with that is once the ROM goes away, so does BASIC, and the CPU starts executing Lord knows what since the RAM isn't initialized. So the actual procedure is to copy the ROM contents into RAM, which is simple enough:

	orcc	#$50	; disable interrupts
	ldx	#$8000	; start of ROM
loop	sta	$FFDE	; enable ROM mapping
	lda	,x	; read byte
	sta	$FFDF	; enable RAM
	sta	,x+	; write byte back, increment pointer
	cmpx	#$FF00	; are we done?
	bne	loop
	andcc	#$AF	; enable interrupts

We don't actually want to copy the full 32K of ROM, since the upper 256 bytes of the memory map is for I/O devices. We also disable interrupts since the default interrupt handlers are in ROM and if an interrupt happens when we have RAM mapped, there may not be an interrupt handler to handle it.

The code is straightforward, simple, and unfortunately, slow. Here's the main loop again, this time with the number of cycles and bytes each instruction takes:

			; cycles	bytes
loop1	sta	$FFDE	; 5		3
	lda	,x	; 4		2
	sta	$FFDF	; 5		3
	sta	,x+	; 6		2
	cmpx	#$FF00	; 4		3
	bne	loop1	; 3		2

The loop is 15 bytes, taking 27 cycles for each iteration. Since we copy one byte per iteration and we have 35,512 iterations, it takes 877,824 cycles to run (there are no pipe lines or caches to worry about, so this will always take 877,824 cycles to run). Given the Color Computer runs at .89 MHz (yes, it's not a fast computer) this is nearly a second to copy 32K of RAM.

Can we do better?

Well, yes. Should we is another matter. I mean, this code is typically run once, so does it matter if it takes a second to run? Meh. It'll take longer to load the code from disk, but hey, I'm doing recreational retro programming and want to have a bit of fun.

The first and easiest optimization is to read and write 16 bits at a time instead of 8. And that's easy enough to do—the 6809 does have a 16-bit accumulator so it's an easy change:

			; cycles	bytes
loop2	sta	$FFDE	; 5		3
	ldd	,x	; 5		2
	sta	$FFDF	; 5		3
	std	,x++	; 8		2
	cmpx	#$FF00	; 4		3
	bne	loop2	; 3		2

The loop now takes 30 cycles per iteration, but it's doing 16-bits per iteration instead of 8. The code now takes 487,680 cycles, which is almost half the time, and we've cut the cycles per byte to 15 from 27, and the size of the code hasn't changed. Not bad for a simple optimization.

But doing 4 bytes per iteration should be better, right? It'll take another register (which we have) and some additional bytes, but yes, it is better:

			; cycles	bytes
loop3	sta	$FFDE	; 5		3
	ldd	,x	; 5		2
	ldu	2,x	; 6		2
	sta	$FFDF	; 5		3
	std	,x++	; 8		2
	stu	,x++	; 8		2
	cmpx	#$FF00	; 4		3
	bne	loop3	; 3		2

Each iteration now takes 44 cycles, but we're moving 4 bytes per iteration, giving us 11 cycles per byte, and it takes a total of 357,632 cycles. Again an improvement but we're starting to hit diminishing improvements. Doing 6 bytes per iteration (still easy to add) takes us down to 9.833 cycles per byte, and 8 bytes per iteration takes us down to 9.24 cycles per byte, but we require the use of the S register (the system stack pointer, which needs to be saved and restored) to do so. It's not worth trying to use the last register available to us (DP) because you can't load it directly. The loop also increases in size, from 19 bytes (shown above) to 23 bytes for the 8-bytes-per-iteration version. Also, the upper address will have to change for the 6 byte version, since 6 doesn't cleanly divide 32,512. It's not a show stopper, since not all the memory in the upper 32K contains useful code, so a few bytes not copied won't crash BASIC.

But we can still do better!

Taking inspiration from “A Great Old-Timey Game-Programming Hack” we can copy 8 bytes per iteration (first, the commented code, then the code with the cycles/bytes columns):

	orcc	#$50	; disable interrupts
	sts	savesp	; we need the S register
	lds	#$FF00-8; and because we're using the stack,
			; we need to start at the top of ROM
			; and work our way down
loop4	sta	$FFDE	; enable ROM mapping
	puls	u,x,y,d	; pull 4 2-byte registers from memory (read memory)
	sta	$FFDF	; enable RAM
	pshs	u,x,y,d	; push 4 2-byte registers to memory (write memory)
	leas	-8,s	; point to next 8-byte block to transfer
	cmps	#$8000-8; are we done?
	bne	loop4
	lds	savesp	; restore S register
	andcc	#$AF	; enable interrupts

The PULS instruction pulls the listed registers off the stack, and the PSHS instruction pushes the listed registers onto the stack. The order of registers in the instructions doesn't matter; they get pushed and pulled such that it all works out.

			; cycles	bytes
loop4	sta	$FFDE	; 5		3
	puls	u,x,y,d	; 13		2
	sta	$FFDF	; 5		3
	pshs	u,x,y,d	; 13		2
	leas	-8,s	; 5		2
	cmps	#$8000-8; 5		4
	bne	loop4	; 3		2

The main loop is now 18 bytes, so it's on par with the third version. But each iteration now takes 49 cycles, but given it moves 8 bytes per iteration, we get an effective rate of 6.125 cycles per byte, and a total time of 199,136 cycles. We could do nine bytes per iteration (as the PSHS and PULS instructions support the DP register) to get us down to 5.666 cycles per byte (184,235 cycles total). We could also add in the CC register for a total of 10 bytes per iteration (5.3 cycles per byte; 172,314 cycles total) but we run the risk of enabling interrupts at the wrong time, unless we disable interrupts at the hardware level (which we can do, but it's more code and more invasive of system state). You can see we'd be getting into diminishing returns again, so I'm happy with just doing 8 bytes per iteration.

Summary of results of copying 32,512 bytes from ROM to RAM
loop	cycles/iteration	cycles/byte	cycles total	bytes/iteration	code size
loop1	27	27.000	877,824	1	15
loop2	30	15.000	487,680	2	15
loop3	44	11.000	357,632	4	19
loop4	49	6.125	199,136	8	18
(theoretical)	53	5.300	172,314	10	18

Is this important these days? Not really. Is it fun? Yes, it certainly beats Enterprise Agile any day of the week.

Discussions about this entry

“We couldn't pause TV and we couldn't just fast forward through the commercials! Gather around kids, and I shall tell more horror tales of the past …”

Over a week ago, I had to order some checks from my bank due to a new recurring expense. My last check I wrote from my checkbook was for some time in 2015. Then one check from 2014, and one from 2013.

Needless to say, I haven't had a need for a checkbook in years.

So the new checkbook arrived (two of them, actually). I recall in the past, they would arrive in the mail in a box sized large enough to hold the checks. But today, they arrived in an unusual format—a flat package about 6½ × 10 × ½ inches (16.5 × 25.5 × 10 mm). Upon opening it, it looked like a book, and stuck to the inside cover were two checkbooks. I pulled them off, and beneath one of them was instructions on how to write a check (with a link to an instructional video)!

I suddenly feel old.

Tuesday, March 07, 2023

So frustrated that I have no one to scream at, which may be the point why it's so hard to get ahold of customer representatives at tech companies these days

I'm so frustrated right now.

Bunny can't receive email, and we have no idea why that is. All we get is that there have been too many attempts to log into her account and she needs to reset the password. Now, her account is with bellsouth.net which is now owned by AT&T but email for customers is handled by Yahoo, but trying to track down a human being to talk to is a Herculean effort these days, and even if we get ahold of someone, can they even help? Forget the left hand not knowing what the right hand is doing, it appears these days that the left hand doesn't even know it has fingers!

Going to the AT&T login page mentions something about currently.com, but going to currently.com goes to yahoo.com (which, to be fair, is handling email for bellsouth.net). Man, is this confusing. We go through the process of changing the password, only to get redirected back to the login page, which fails because the password we set seems to be incorrect, and thus, we get more and more failed logins until we're forced to change the password yet again.

And the cycle continues.

Doing a search shows that we aren't alone in this, and that this issue has been an ongoing problem for several years now with no solution in sight.

Does anybody at AT&T or Yahoo know what's going on?

To add further fuel, I can't find the current server settings in the Apple Mail application, adding to my frustration.

Eventually, I gave up and set her up with Fastmail. It's not as big as Google, and it's a pay service, so there's a decent chance that talking to a human is possible. Also, it was nearly painless to set up. I say “nearly painless” because it did take me several minutes to figure out the DNS settings I needed to give Bunny her own sub-domain in conman.org (because if she's going through the pain of changing an email address from one she's used for years, I'd rather she use a domain not in the control of the email company in the off chance we need to switch providers so she can keep the same email address, and I don't want to hand off my own email to Fastmail since I'm comfortable using mutt directly on my server). Then there was one file to download that installed information on her Mac laptop that informed the Apple Mail application of the Fastmail settings and that was that. She was good to go.

It just sucks that she has to change her email address.

Monday, March 06, 2023

Another attempt at a “unit test”

Or, “What is a ‘unit test,’ part III”

The reactions to my previous post were interesting—it wasn't a “unit test.” At best, it might have been an “integration test” but because it involved actual work (i.e. interaction with the outside world via nasty nasty side effects, aka I/O) it immediately disqualified it as a “unit test.” And to be honest, I was expecting that type of reaction—it appears to me that most unit test proponents tend to avoid such “entanglements” when writing their “battle tested” code (but I'm also willing to admit that's the cynical side of me talking). There were also comments about how 100% code coverage was “unrealistic.”

Sigh.

One respondent even quoted me out of context—“… that we as programmers are not trusted to write code without tests …” and cut the rest of the sentence: “… yet we're trusted to write a ton of code untested as long as such code is testing code.” Which was my cynical take that the “unit tests” (or the code that implements “unit tests” ) are, themselves, not subjected to “unit tests.” Something I kept trying to impart to my former manager, “stop taking the unit tests as gospel! I don't even trust them!” (mainly because the business logic of the project was convoluted and marketing kept using different terms from engineering, at least engineering in my department)

But when I left off, I said there was one final function that should fit as a “unit,” and thus, perfect for “unit testing.” Again, it's from my blog engine and the function in question deals with parsing a request, like “2001/10/02.2-11/03.3” (which requests all blog posts starting from the second post on October 2^nd to the third post of November 3^rd, 2001). or “2001/11/04.2” (the second post from November 4^th, 2001).

The function tumbler_new() does no I/O (that is—no disk, network or console I/O), touches no global variables, only works with the data given to it and does some covoluted parsing of the input data—if this isn't a good candidate for “unit tests” then I don't know what is.

The tests were straightforward—a bunch of failure cases:

  tap_assert(!tumbler_new(&tumbler,"foo/12/04.1",&first,&last),"non-numberic year");
  tap_assert(!tumbler_new(&tumbler,"1999/foo/04.1",&first,&last),"non-numeric month");
  tap_assert(!tumbler_new(&tumbler,"1999/12/foo.1",&first,&last),"non-numeric day");
  tap_assert(!tumbler_new(&tumbler,"1999/12/04.foo",&first,&last),"non-numeric part");
  tap_assert(!tumbler_new(&tumbler,"1998",&first,&last),"before the start year");
  tap_assert(!tumbler_new(&tumbler,"1999/11",&first,&last),"before the start month");
  tap_assert(!tumbler_new(&tumbler,"1999/12/03",&first,&last),"before the start day");
  tap_assert(!tumbler_new(&tumbler,"1999/12/04.0",&first,&last),"part number of 0");
  tap_assert(!tumbler_new(&tumbler,"2023",&first,&last),"after the end year");
  tap_assert(!tumbler_new(&tumbler,"2022/11",&first,&last),"after the end month");
  tap_assert(!tumbler_new(&tumbler,"2022/10/07",&first,&last),"after the end day");
  tap_assert(!tumbler_new(&tumbler,"2022/10/06.21",&first,&last),"after the end part");
  tap_assert(!tumbler_new(&tumbler,"1999/00/04.1",&first,&last),"month of 0");
  tap_assert(!tumbler_new(&tumbler,"1999/13/04.1",&first,&last),"month of 13");
  tap_assert(!tumbler_new(&tumbler,"1999/12/00.1",&first,&last),"day of 0");
  tap_assert(!tumbler_new(&tumbler,"1999/12/32.1",&first,&last),"day of 32");
  tap_assert(!tumbler_new(&tumbler,"1999/12/04.0",&first,&last),"part of 0");
  tap_assert(!tumbler_new(&tumbler,"1999/12/04.24",&first,&last),"part of 24");
  tap_assert(!tumbler_new(&tumbler,"2010/07/01-04/boom.jpg",&first,&last),"file with range");
  tap_assert(!tumbler_new(&tumbler,"2010/7/1-4/boom.jpg",&first,&last),"file with redirectable range");

Plus a bunch of tests that should pass:

  test("first entry","1999/12/04.1",&(tumbler__s) {
    .start    = { .year = 1999 , .month = 12 , .day = 4 , .part = 1 },
    .stop     = { .year = 1999 , .month = 12 , .day = 4 , .part = 1 },
    .ustart   = UNIT_PART,
    .ustop    = UNIT_PART,
    .segments = 0,
    .file     = false,
    .redirect = false,
    .range    = false,
    .filename = ""
  });
  
  test("some mid entry","2010/07/04.15",&(tumbler__s) {
    .start    = { .year = 2010 , .month = 7 , .day = 4 , .part = 15 },
    .stop     = { .year = 2010 , .month = 7 , .day = 4 , .part = 15 },
    .ustart   = UNIT_PART,
    .ustop    = UNIT_PART,
    .segments = 0,
    .file     = false,
    .redirect = false,
    .range    = false,
    .filename = ""
  });
  
  test("last entry","2022/10/06.20",&(tumbler__s) {
    .start    = { .year = 2022 , .month = 10 , .day = 6 , .part = 20 },
    .stop     = { .year = 2022 , .month = 10 , .day = 6 , .part = 20 },
    .ustart   = UNIT_PART,
    .ustop    = UNIT_PART,
    .segments = 0,
    .file     = false,
    .redirect = false,
    .range    = false,
    .filename = ""
  });
  
  test("requesting a file","2010/07/04/boom.jpg",&(tumbler__s) {
    .start    = { .year = 2010 , .month = 7 , .day = 4 , .part =  1 },
    .stop     = { .year = 2010 , .month = 7 , .day = 4 , .part = 23 },
    .ustart   = UNIT_DAY,
    .ustop    = UNIT_DAY,
    .segments = 0,
    .file     = true,
    .redirect = false,
    .range    = false,
    .filename = "boom.jpg",
  });

  /* ... other tests ... */

With this function checking the results:

static void test(char const *tag,char const *tum,tumbler__s const *result)
{
  tumbler__s  tumbler;
  
  assert(tag    != NULL);
  assert(tum    != NULL);
  assert(result != NULL);

  tap_plan(10,"%s: %s",tag,tum);
  tap_assert(tumbler_new(&tumbler,tum,&first,&last),"create");
  tap_assert(btm_cmp(&tumbler.start,&result->start) == 0,"start date");
  tap_assert(btm_cmp(&tumbler.stop,&result->stop) == 0,"stop date");
  tap_assert(tumbler.ustart == result->ustart,"segment of start");
  tap_assert(tumbler.ustop == result->ustop,"segment of stop");
  tap_assert(tumbler.segments == result->segments,"number of segments");
  tap_assert(tumbler.file == result->file,"file flag");
  tap_assert(tumbler.redirect == result->redirect,"redirect flag");
  tap_assert(tumbler.range == result->range,"range flag");
  tap_assert(strcmp(tumbler.filename,result->filename) == 0,"file name");
  tap_done();
}

I ended up with a total of 328 tests and of the three attempts I made, this one feels like the only one that was worth the effort—it's a moderately long function [Moderately long? It's 450 lines long! —Editor] [But it does one thing, and one thing well—it parses a request! —Sean] [450 lines! —Editor] [I'd like to see you write it then! —Sean] [… Okay, I'll shut up now. —Editor] that implements some tricky logic and deal with some weird edge cases. If I ever go back to rework this code (and I've only revised this code once in the 23 years it's been used, way back in 2015—it was a full rewrite of the function) the tests could be useful (if I'm honest with myself, and the API/structure doesn't change). ~~And from looking over the test cases, I can see that I could get rid if .segments from the structure, so there's that.~~(Seems I was wrong---the .segments field is needed for tumbler_canonical())

Overall, I'm still not entirely sure about this “unit test” stuff, especially since “unit” doesn't have a well defined meaning. In my opinion, I think it works best for functions that do pure processing (no interaction with the outside world) and that implement some complex logic, like parsing or business logic. Back when I was at The Enterprise, had we but one function (or entry point) that just implemented all the business logic from data gathered from the request, it would have have made testing so much easier. But “unit tests” for all functions? Or modules? Or whatever the XXXX a “unit” is? No. Not for obvious code, or for for code that interacts with external systems (unless required because human lives are on the line). I'm not saying no to tests entirely, but to the slavish adherence to testing for its own sake.

Or maybe, instead of having AI write code for us, have it write the test cases for us, intead of the future I'm cynically seeing—where we write the test cases for AI written code.

Discussions about this entry

Another attempt at a “unit test” | Lobsters

Wednesday, March 01, 2023

I'm seriously wondering who is trolling who at this point

I have a Gmail account. I signed up early enough to get my name as an email address at Gmail. But I never use it for anything, so by default, anything that arrives there is either spam or misaddressed. I will occasionally check it, and I found two emails from one Trudy XXXXXXXXXXX. The first one:

From
Trudy XXXXXXXXXXX <XXXXXXXXXXXXXXXXXXXXXX> (an address from a Tennessee school)

To
Sean Conner <sean.conner@gmail.com>, (and other addresses to the same Tennesee school, I checked)

Subject
IMPORTANT DEVICE INFORMATION (Waiver)

Date
Mon, 20 Feb 2023 15:51:00 -0500

Parents/Guardians:

Please check your child's Power School account to see if your child has a hold due to a damaged, stolen or lost device. If your child has a damaged, lost, stolen device, you may be eligible to fill out a waiver to allow your child to get a device for no charge.

-The waiver is limited to devices only. Keyboards, cases and chargers are not covered.

If you have already filled out a waiver, or your child's device has been returned to school in good working condition, please disregard this message.

Thursday, February 23, 2023, is our Black History Program. You will be allowed to fill out the waiver after each program (morning or afternoon show).

Part of the waiver agreement requires you to have custody of your child as shown in Power School, provide a valid ID, and be prepared to watch a short 2.5-minute video at the time of completing the waiver.

Morning show is at: 9:15 am
Afternoon show is at: 2:00pm

Thank you 🙂

[School Logo]

Trudy XXXXXXXXXXXXX
School Counselor
XXXXXXXXXX Elementary
XXXXXXXXXXXXXXXXXXXXXX
Memphis, TN 38116
901-XXXXXXXX (School)
901-XXXXXXX (Fax)
XXXXXXXXXXXXXXXXXXXXXX
"Every child deserves to be a champion: an adult who will never give up on them, who understands the power of connection and insists they become the best they can possibly be"-Rita Pierson

Together, we MUST BELIEVE.

Together, we WILL ACHIEVE.

Together, we ARE REIMAGINING 901!

Does the Sean Conner who lives in Tennesee not know his own Gmail address? I always wonder about that. But regardless, I decided to reply with a bit of surrealism.

From
Sean Conner <sean.conner@gmail.com>

To
Trudy XXXXXXXXXXX <XXXXXXXXXXXXXXXXXXXXXX>

Subject
IMPORTANT DEVICE INFORMATION (Waiver)

Date
Wed, 1 Mar 2023 14:48:00 -0500

One question I have is—what do I do if I don't have a child? The device is fine, but I don't have a kid that uses it. Do I still need a waiver?

The second question I have is—why is my non-existent child enrolled in a school in Tennessee when I live in Florida?

Thank you.

I expected no reply, or maybe a reply like “Sorry to have bothered you.” What I did not expect was this reply:

From
Trudy XXXXXXXXXXX <XXXXXXXXXXXXXXXXXXXXXX>

To
Sean Conner <sean.conner@gmail.com>

Subject
RE: EXTERNAL - Re: IMPORTANT DEVICE INFORMATION (Waiver)

Date
Wed, 1 Mar 2023 14:55:00 -0500

Hello,

If you have device that belongs to XXXXXX County Schools, we will need to arrange a way to get the device back or you will need to pay for the device.

You cannot get a waiver if your child no longer attends XXXX
Do you know if you are listed as a contact for a relative of step child who attends XXXXXXXXXX Elementary? If so what are the names?

You will need to contact the parents/ guardians and ask them to remove you from their child’s contact.

I hope that I was able to assist you

Sent from Mail for Windows

What? My email was taken seriously? Am I being trolled? Who is trolling who?

Wow.

So anyway, the other email I received from Trudy (I mean, aside from the reply I received for the first email) was this one about current attentance policies:

From
Trudy XXXXXXXXXXX <XXXXXXXXXXXXXXXXXXXXXX>

To
Sean Conner <sean.conner@gmail.com>, (and other addresses to the same Tennesee school, I checked)

Subject
School Wide Attendance/Chronic Absence IMPORTANT

Date
Mon, 20 Feb 2023 17:42:00 -0500

Greetings XXXXXXXXXX Family!

Last week we had two great days of overall school attendance, however two days is just not enough. Please make sure that you are sending your child to school every day and on time. Please review the attendance policy about excused absences. Moving forward, we will adhere strictly to the attendance policy when excusing absences.

Attendance and Excuses (Policy #6014) The XXXXXX County Board of Education believes that regular attendance is a necessary requirement of all students. All students are expected to attend school on each day that school is officially in session and remain at school for the entirety of the school day. Only the following reasons will be considered for excused absences:

Illness, injury, pregnancy, homebound circumstance, or hospitalization of student. The District may require a parent conference and/or physician verification to justify absences after the accumulation of ten (10) days of absence during a school year. Notes must be date specific and will be required for subsequent absences beyond ten (10) days.

Death or serious illness within the student's immediate family.

When the student is officially representing the school in a school sponsored activity or attendance at school-endorsed activities and verified college visits.

Special and recognized religious holidays regularly observed by persons of their faith. Any student who misses a class or day of school because of the observance of a day set aside as sacred by a recognized religious denomination of which the student is a member or adherent, where such religion calls for special observances of such day, shall have the absence from that school day or class excused and shall be entitled to make up any school work missed without the imposition of any penalty because of the absence.

A court order; a subpoena; and/or a legal court summons.

Extenuating circumstances over which the student has no control as approved by the principal.

If a student's parent, custodian or other person with legal custody or control of the student is a member of the United States Armed Forces, including a member of a state National Guard or a Reserve component called to federal active duty, the student's Principal shall give the student: a. An excused absence for one (1) day when the student's parent, custodian or other person with legal custody or control of the student is deployed; b. An additional excused absence for one (1) day when the student's parent, custodian or other person with legal custody or control of the student returns from deployment; and c. Excused absences for up to ten (10) days for visitation when the student's parent, custodian or other person with legal custody or control of the student is granted rest and recuperation leave and is stationed out of the country. d. Excused absences for up to ten (10) days cumulatively within the school year for visitation during the deployment cycle of the student's parent, custodian or other person with legal custody or control of the student. Total excused absences under this section (c) and (d) shall not exceed a total of ten (10) days within the school year. The student shall provide documentation to the school as proof of the deployment of the student's parent, custodian or other person with legal custody or control of the student.

Participation in a non-school-sponsored extracurricular activity. A school principal or the principal's designee may excuse a student from school attendance to participate in a non-school-sponsored extracurricular activity, if the following conditions are met: (1) The student provides documentation to the school as proof of the student's participation in the non-school-sponsored extracurricular activity; and (2) The student's parent, custodian, or other person with legal custody or control of the student, prior to the extracurricular activity, submits to the principal or the principal's designee a written request for the excused absence. The written request shall be submitted no later than seven (7) business days prior to the student's absence.

The written request shall include:

The student's full name and personal identification number;

The student's grade;

The dates of the student's absence;

The reason for the student's absence; and

The signature of both the student and the student's parent, custodian, or other person with legal custody or control of the student. The principal or the principal's designee shall approve, in writing, the student's participation in the non-school-sponsored extracurricular activity. The principal may limit the number and duration of non-school-sponsored extracurricular activities for which excused absences may be granted to a student during the school year; however, such the principal shall excuse no more than ten (10) absences each school year for students participating in non-school-sponsored extracurricular activities. Students receiving an excused absence under this section shall have the opportunity to make up school work missed and shall not have their class grades adversely affected for lack of class attendance or class participation due to the excused absence.

A written statement within two (2) school days of the student's return to school shall be required from the parent or guardian explaining the reason for each absence. If necessary, verification is required from an official source to justify absences. All absences other than those outlined above shall be considered unexcused.

[School Logo] Trudy XXXXXXXXXXXXX
School Counselor
XXXXXXXXXX Elementary
XXXXXXXXXXXXXXXXXXXXXX
Memphis, TN 38116
901-XXXXXXXX (School)
901-XXXXXXX (Fax)
XXXXXXXXXXXXXXXXXXXXXX
"Every child deserves to be a champion: an adult who will never give up on them, who understands the power of connection and insists they become the best they can possibly be"-Rita Pierson

Together, we MUST BELIEVE.

Together, we WILL ACHIEVE.

Together, we ARE REIMAGINING 901!

One thing stood out to me—the family name given in the greeting doesn't match my family name, nor does it match any of the family names of any of the other recipients on the email. Otherwise, much like the first email, I have to wonder why I'm receiving this. So I decided to reply to this one with a bit more sarcasm:

From
Sean Conner <sean.conner@gmail.com>

To
Trudy XXXXXXXXXXX <XXXXXXXXXXXXXXXXXXXXXX>

Subject
School Wide Attendance/Chronic Absence IMPORTANT

Date
Wed, 1 Mar 2023 14:55:00 -0500

I must say, it appears that excused absences got more lenient over the years since I was in school. Back when I was in school, excused absences were only allowed with a 10 day prior notice, or appropriate documentation from a doctor, law enforcement officer, or pardon from the governor. What is it with these weak policies towards absences? This is intolerable for my non-existent child in a school three states away!

Here, I expected Trudy to clue in—I mean, “pardon from the governor?” Who ever heard of such a policy for a school? But again, not to be outdone, I got this back from Trudy:

From
Trudy XXXXXXXXXXX <XXXXXXXXXXXXXXXXXXXXXX>

To
Sean Conner <sean.conner@gmail.com>

Subject
RE: EXTERNAL - Re: School Wide Attendance/Chronic Absence IMPORTANT

Date
Web, 1 Mar 2023 14:57:00 -0500

Thank you for your concern, please make sure that you have withdrawn your child from XXXX.

Thank you

Sent from Mail for Windows

…

I … I have no words.

What have I gotten myself into?

Update on Thursday, March 2^nd, 2023

A few more emails exchanged, and Trudy and I have straightened things out.

Friday, February 24, 2023

A branchless segment of code to generate a printable hexadecimal value

I was an avid fan of assembly language back in my youth and I did a lot of it. And in that time, if I needed to convert a 4-bit quantity to a hexadecimal character, I would write the obvious code:

	; x86 code
		add	al,'0'
		cmp	al,'9'	; if '0'-'9', no adjustment needed
		jbe	skip	; otherwise, we need to adjust
		add	al,7	; the resulting character by 7
				; to get 'A'-'F'
skip:

Eight bytes and a branch instruction, and not many ways I could see to improve on that, until the other day when I came across this bit of code:

	; x86 code
		add	al,90h
		daa
		adc	al,40h
		daa

Not only does this convert a 4-bit value to a hexadecial character, but it's two bytes shorter and it's branchless!

Now, some might say this abuses the DAA instruction, but it works. And how it works is pretty clever I think. The DAA instruction exists to allow BCD arithmetic (back when it was a thing). For each 4-bits in a byte, the DAA instruction will check to see if it's in the range of 10 to 15 and if so, add 6 to that 4-bit value to bring it back into the 0 to 9 range, and propagate a carry bit (well, it's a bit more involved than that, but that will suffice for this post—you can check my MC6809 emulator for the gory details of the DAA instruction). By adding 0x90 (or 144 in decimal) to a 4-bit value then using DAA, a carry bit will be propagated if the initial value was 10 to 15; otherwise there's no carry to propagate. The ADC of 0x40 (or 64 decimal) will then add any carry of the previous two instructions into the lower four bits of the result, and the DAA will then adjust the upper 4-bits to be either 0x3 or 0x4 due to the previous addition of 0x90 (which causes the number to act like a negative number if the initial value was bewteen 0 and 9). And because of the carry if the initial 4-bit value was between 10 to 15, you get the required adjustment of 7 needed for values of 10 through 15.

This means the result is 0x30 to 0x39 (the ASCII values of “0” to “9”) of the 4-bit values of 0 through 9, or 0x41 to 0x46 (the ASCII values of “A” to “F”) for values 10 through 15.

Quite ingenious really.

I found reference to what may be the origin of this sequence: the article “A Design Philosophy for Microcomputer Architectures” from the February 1977 edition of Computer (the code appears on the third page of the article), but it's unclear if the author came up with this on his own, or it was a known sequence at the time.

I just wish I found out about it earlier.

Discussions about this entry

Thursday, February 23, 2023

A breakdown of the triple-star pointer

I few days ago I read “Lessons learnt while trying to modernize some C code” (via Lobsters) and one of the problems of C stated stood out to me: “Avoid constructs like char ***. I thought it was a joke, but people do pass around char *** and it’s insane—almost impossible to comprehend why do you need a pointer to a pointer to a pointer.” Yes, it happens, but come on! That doesn't happen often enough to complain about!

And then I found one in my own code!

Sigh.

Okay, at least I can explain why I needed a char ***. It's not insane, and it's not impossible to comprehend why. I'll start with char *'. In C, that means “string” (the exceptions are just that—exceptions). We can replace char * with typedef char *cstring which gets rid of one “*”, leaving effectively cstring **.

Now, when you see char **, say in int main(int argc,char **argv), it generally has the meaning of an array of strings: int main(int argc,char *argv[]). Sometimes it could mean just a pointer to a pointer, but I'm using the “array of strings” meaning in my code. Translated using the custom type I defined above, char ** becomes becomes cstring [] and char *** becomes cstring *[]—a pointer to an array of strings. And this idiom, when it happens, usually means the callee is going to allocate the memory for the array of strings and return it via the pointer. Which is exactly what the function I wrote does.

So when I expect a char *** here, what I'm asking for is a pointer to an array of strings (aka character pointers or character arrays). The only thing insane about this is the syntax, and maybe the semantics (pointers and arrays are near enough the same that it's dangerous) but I've been working with C long enough that I just kind of accept it.

Now, just don't ask about char ****—that's just silly talk!

Discussions about this entry

Thursday, February 16, 2023

I guess now Bunny can add “upholsterer” to her list of hobbies

A few weeks ago, the top arm coverings of my office chair basically crumbled and fell off.

[Picture of a chair with arms, but the arms are missing a cover.] Black always makes things slimmer. Only in this case, it is slimmer without the rubber covering.

The old coverings were some combination of rubber and plastic and I guess over time, they just became brittle or dried out, and fell apart. This exposed the underlying hard plastic frame underneath. It wouldn't be that bad actually, except for all the square holes, used to both lessen the amount of hard plastic required, and to give the old covers something to grip onto.

[Closeup of an uncovered arm on the office chair showing a surface with cutouts to save material, but makes it uncomfortable to use as an arm rest.] It's a combination arm rest and cheese grater!

Resting my arms on the bare arm rests is uncomfortable—it's not exactly cutting into my skin, but I can feel the square holes which is unpleasant, and left a square pattern on my arms. My idea was to take some foam and wrap some cloth type material around it and the plastic frame. But it was Bunny who made the new covers from material lying about Chez Boca.

[Picture of a new arm cover for an office chair.] Grab a strobe black light, turn up the techo, and we can have a rave!

It's basically a tube of cloth wrapping the foam, with some extra material folded back onto itself to form some flaps to go around the ends of the arm rests. Here I am demonstrating how it works with my fingers.

[Picture demonstrating the flap on the new arm covers to hold it onto the chair.] Makes for a lousy puppet. Maybe with some googly eyes?

The material has some stretch ability, which helps to keep it on the arm rests.

[Picture of a chair with arms, now with the new arm covers.] Is it not nifty?

It adds a nice bit of color to the chair, and it's a lot more confortable than the old covering. Nice job indeed!

The Boston Diaries

Monday, March 13, 2023