Jeff Epler's blog

6 November 2020, 1:54 UTC

Head Scratching C(++) Bug


What's wrong with the following loop? I stared at it for quite some time before finding the bug in my code, all too ready to exclaim "it's a compiler bug":

/* n is a parameter of type size_t */
/* table is a pointer to int such that table[0] .. table[n-1] are all valid indices */
for(size_t i = 0; i < n; i++) {
    if(table[i] == needle) return i;
}

Instead of terminating after at most n iterations, the loop continued indefinitely, eventually returning some nonsense value where another memory location matched the needle value.

Give up? The problem's nothing to do with the loop, but with what came (didn't come) after it:

size_t find_in_table(int *table, size_t n, int needle) {
    for(size_t i = 0; i < n; i++) {
        if(table[i] == needle) return i;
    }
}

There's no return statement after the loop. If the loop terminates, it reaches the end of a non-void function without returning a value. This is undefined behavior. Therefore, the compiler-author logic goes, it must be the case that the loop can never terminate due to the loop condition; it must only terminate by the return statement inside the loop. (Stated in another way, the "undefined behavior" is to continue to run the loop.)

Without the final return (e.g., return (size_t)-1;), the comparison i < n is completely eliminated at typical optimization levels. Even weirder, you can get the program to print that (say) i==5, n==4, and that i<n is true!

I think gcc has an enabled-by-default warning for this, but either it's disabled by my project's CFLAGS or I overlooked it in a torrent of other compiler output.

Without looking beyond the loop or if you're thinking with the mindset that a missing return statement's undefined behavior is "returns an arbitrary value", you don't think about things like this. This is a very easy mistake to make, since it is also a pretty good model of what a modern compiler will do at "for better debugging" optimization levels, as well as what the "C is portable assemblre" moto asks us to falsely believe. No, in reality, C(++) is a slippery language. While it's not a bet you could settle in the negative, I bet there's at least one security bug out there due to this undefined behavior and the way that gcc transforms a finite loop into an infinite one.

My recommendation?

Pay attention to compiler diagnostics. Enable more of them. Understand what the diagnostic is saying, then make an appropriate response. Get your editor's help to parse error lists and make sure you don't miss any.

[permalink]

1 November 2020, 16:18 UTC

wwvbgen updates


I occasionally maintain a Python module called wwvbpy, which can generate WWVB timecodes for any desired time.

The change to winter (standard) time in the US is the perfect moment to review what's up with wwvpy and correct any discovered problems. (in fact, I was prompted by Chris's remark that his WWVB receiver had too eagerly applied the end of DST—as soon as GMT midnight rolled around, I think. Oops!)

This time around, here are the minor tweaks I made:

  • Update license to GPL3+ (was GPL2+)
  • Revamp how DUT1 ("iersdata") is gathered and harmonized
  • Convert tests to run as unittests; fix timezone test problems
  • Add github actions for CI
  • Add github "cron" to update iersdata
  • Add "expected output" tests for phase data, though this is just self-generated, not independently-generated data

WWVB timecode: year=20 days=306 hour=06 min=50 dst=1 ut1=-200 ly=1 ls=0 --style=duration
'20+306 06:50  852522222822222255282255222228255222252822522225282222252258

[permalink]

7 September 2020, 14:31 UTC

Pi Zero W USB Proxy


I'm not sure exactly what to call it, but here's a little something I set up this weekend.

On my Linux desktop, I have occasional problems where being stopped at the debugger prompt for a plugged-in USB device hoses the whole computer. The problem waxes and wanes but on a particularly frustrating day I decided that maybe a Pi was the answer to the problem.

Using screen I can access the USB-serial devices on the pi, and using sshfs I can access the files. If the whole pi freezes, I can just reboot it with essentially no harm done.

I selected a Pi Zero W with a Zero4U hub and Adafruit MiniPiTFT 1.14" attached. To a base raspbian lite system I added some software, including tio, udiskie, screen, and Adafruit Blinka; enabled ssh access and disk mounting by the pi user, and set up GNU screen and my custom script for the LCD which is (confusingly) also called screen.

The screen shows information about each of the 4 USB connectors. In brackets "S" is shown if there is a serial device; "D" is shown if there's a partitioned disk, "d" if there's an unpartitioned disk; and "M" is shown if it is mounted. After that, the device name is shown.

Automount can be toggled with the B button (silk screen 23) and any non-mounted disks can be mounted with the A button (silk screen 24)

So far I've only used it lightly, but if it prevents a single crash of my desktop, it will be worth it.

This isn't a detailed guide so a lot of the setup is omitted. However, here are the scripts that are the essential parts:

[permalink]

27 August 2020, 21:10 UTC

GPS and relativity


This is info I've dug up a few times, but it's getting harder to find. Let's put it here, maybe I'll remember its on my own website. The ever-helpful leapsecond.com has a copy of an article from lsu.edu stating:
At the time of launch of the first NTS-2 satellite (June 1977), which contained the first Cesium clock to be placed in orbit, there were some who doubted that relativistic effects were real. A frequency synthesizer was built into the satellite clock system so that after launch, if in fact the rate of the clock in its final orbit was that predicted by GR, then the synthesizer could be turned on bringing the clock to the coordinate rate necessary for operation. The atomic clock was first operated for about 20 days to measure its clock rate before turning on the synthesizer. The frequency measured during that interval was +442.5 parts in 1012 faster than clocks on the ground; if left uncorrected this would have resulted in timing errors of about 38,000 nanoseconds per day. The difference between predicted and measured values of the frequency shift was only 3.97 parts in 1012, well within the accuracy capabilities of the orbiting clock. This then gave about a 1% validation of the combined motional and gravitational shifts for a clock at 4.2 earth radii.
It also contains supporting scans of NASA Technical Memorandum 78104, 1977 9th annual PTTI, NTS-2 report showing these statements, although the Technical Memorandum does not state whether the initial pre-tuning value was really due to "doubts" that relativistic effects were real, as compared to other operational reasons.

An earlier document, NTS-2 Cesium Bean Frequency Standard for GPS states (errors mine)

The NTS-2 program office at NRL was tasked by GPS NAVSTAR program office to generate a 10.23 MHz frequency for use with the Pseudo Random Noise System (PRNSA) onboard the NTS-2 Satellite. Frequency requrements for the NTS-2 Orbit Determination and Tracking Systerm (ODATS) was 5MHz with a tunable ΔF offset of approximately +1 × 10-9 with a resolution of approximately 3 × 10-12. The ΔF offset was to compensate for relativistic effects and could not be accomplished by offsetting the cesium standard which has a tuning range of ± 1 × 10-11. The relativistic offset was later added to the 10.23MHz requirement.
We might try to detect a hint of emotion in "The offset was …later added to the requirement".

Citing "Alley, C., “Proper time experiments in gravitational fields with atomic clocks, aircraft, and laser light pulses”, in Meystre, P., and Scully, M.O., eds., Quantum Optics, Experimental Gravitation, and Measurement Theory", we have

There is an interesting story about this frequency offset. At the time of launch of the NTS-2 satellite (23 June 1977), which contained the first Cesium atomic clock to be placed in orbit, it was recognized that orbiting clocks would require a relativistic correction, but there was uncertainty as to its magnitude as well as its sign. Indeed, there were some who doubted that relativistic effects were truths that would need to be incorporated!

Alley: (again, errors mine)

There was considerable uncertainty among the Air Force and contractor personnel designing and building the system whether these effects were being correctly handled, and even, on the part of some, whether the effects were real. The last group was not satisfied until a gravitational frequency shift was measured with a GPS test satellite called NTS-2 by a group at the Naval Research Laboratory in 1977.
Alley cites T. McCaskill, J. White, S. stebbins, and J. Buisson, NTS-2 frequency stability results, "Proceedings, 32nd Annual Symposium, on Frequency Control," U. S. Army Electronics Research and Development Command, Fort Monmouth, N.J. (1978), a different paper with many of the same names as the first Technical Memorandum. However, I don't see that the citation supports the "considerable uncertainty" nor that any doubted "whether the effects were real". It just states that "the Einstein relativistic clock effect was verified to less than one-half percent".

So, left without a citation to follow, I am still in doubt as to whether there were doubters of general relativity on the project. Rather, except for the resigned voice that the offset was "later added" everything seems consistent with: GR (at least once the issue was raised) was assumed correct, but for other reasons (such as synchronizing it with the ground based cesium clocks before launch) the system was built with two modes, and that a story about doubters grew in the retelling.

Files currently attached to this page:

1977ptti.conf..637W.pdf2.3MB
1978-PTTI-v9-NTS-2.pdf1.7MB
Ashby2003_Article_RelativityInTheGlobalPositioni.pdf460.8kB
a088092.pdf1.1MB
alley1983.pdf7.8MB

[permalink]

18 August 2020, 1:55 UTC

Some notes on the Si5351a


Si5351 "XA" can be driven by a clock signal (25/27 MHz, 1Vpp)
    source: [2] p23, figure 14

Internet commenters report success driving it with a much wider frequency range
as well as successfully exceeding the specified PLL range.  Inputs from 3MHz to
146MHz and PLL frequencies from 168 to 1168MHz were tested.
    source: [1]

intermediate PLL frequency:
    600 to 900 MHz [3] p2
    divider range 15 + 0/1048575 .. 90
    "integer divide" FBA_INT flag is for _EVEN_ integers [3] p4

multisynth:
    valid dividiers are 4, 6, 8, 8 + 1/1048575 ... 2048
    "integer divide" FBA_INT flag is for _EVEN_ integers [3] p6

[1]: http://www.simonsdialogs.com/2018/11/si5351a-any-frequency-cmos-clock-generator-and-vco-specifications-myths-and-truth/
[2]: https://www.silabs.com/documents/public/data-sheets/Si5351-B.pdf (rev 1.3)
[3]: https://www.silabs.com/documents/public/application-notes/AN619.pdf Manually Generating an Si5351 Register Map rev 0.8

[permalink]

16 August 2020, 18:05 UTC

Si5351 Frequency Planner in Python


The Si5351 and related clock generators are very flexible, but they are a bit cumbersome to "program".

The basic design of the Si5351 is that an incoming frequency is first multiplied to create a high internal frequency (nominally in the range from 600MHz to 900MHz), then divided to create an output frequency. The multipliers and dividers have restrictions on their ranges, there are just 2 PLLs but 3 output clocks, and certain types of configurations (e.g., "divisor is an integer multiple of 2") are said to give lower jitter outputs than others.

The datasheet advising users on how to create their own register values is very complicated and some of the parts resist comprehension even after multiple readings. Thie chip maker Silicon Labs provides a graphical closed source Windows program for generating register maps, though some internet commenters regard it as buggy.

This program represents my own effort to create a frequency planner. It neglects some datasheet rules, mostly related to output frequencies above 50MHz or so. It tries to

  • Favor lower-jitter configurations where possible
  • Favor making the first-listed frequency as accurate as possible
  • Try each combination of ways to allocate output clocks to the PLLs
  • Obey the datasheet restrictions as I've understood them
  • Do all arithmetic as infinite precision arithmetic, not floating point
It does not
  • Implement the divisor rules for extremely fast clocks
  • Implement the divisor rules for higher numbered outputs on 20QFN packages

For exact input clocks such as 25MHz, it is surprisingly hard to find a "plausible" frequency that is inexact, and even harder to find a "plausible" frequency that is less exact than your reference clock. I didn't actually find a case where the error is not much smaller than the frequency stability of any reference I'd plausibly have access to.

(Of course, if you measure your reference clock as 25MHz + 13.37Hz and plug that in as the --input-freq then almost everything is related to that clock inexactly, so the fact that the clocks will still be really, really close to the requested value is very nice.)

It does not directly create a register map, but the values shown are easy enough to convert to the form used in the CircuitPython adafruit_si5151 library. Sadly, as CircuitPython does not support the fractions module, it's not currently feasible to run this code on a CircuitPython board directly controlling the si5351 chip.

Example:

Generate 315M/88 (NTSC colorburst), 4.43361875M (PAL colour carrier), 25.8048M (UART clock) all exactly from a 25MHz reference clock or crystal. However, the PAL colour carrier will have more jitter since it uses a fractional divisor:

$ ./party.py 315M/88 4.43361875M 25.8048M
Input frequency: 25000000 (25000000.0)
Frequency plan score: 10.38

PLL A:
Frequency plan type: Fractional multiplier, double integer divisor (1)
Multiplier = 126/5 (25.2)
Intermediate frequency = 630000000 (630000000.0)

Desired output frequency: 39375000/11 (3579545.4545454546)
Divider = 176 (176.0)
Exact
r_divider = 0 (/ 1)


PLL B:
Frequency plan type: Fractional multiplier, fractional divisor (5)
Multiplier = 12059443/500000 (24.118886)
Intermediate frequency = 602972150 (602972150.0)

Desired output frequency: 17734475/4 (4433618.75)
Divider = 136 (136.0)
Exact
r_divider = 0 (/ 1)

Desired output frequency: 25804800 (25804800.0)
Divider = 12059443/516096 (23.366666279141864)
Exact
r_divider = 0 (/ 1)

Generate pi MHz from a 25MHz reference clock or crystal (error: 27.8 nano Hz)

$ ./party.py 3.1415926535898M
Input frequency: 25000000 (25000000.0)
Frequency plan score: 1.00

PLL A:
Frequency plan type: Fractional multiplier, fractional divisor (5)
Multiplier = 24 (24.0)
Intermediate frequency = 600000000 (600000000.0)

Desired output frequency: 15707963267949/5000000 (3141592.6535898)
Divider = 40306053/211042 (190.98593171027568)
Actual output frequency: 42208400000000/13435351 (3141592.653589772)
Relative Error: -8.83757e-15
Absolute Error: 2.78e-08Hz
r_divider = 0 (/ 1)

The source is available in a github gist:

[permalink]

18 July 2020, 13:21 UTC

Quad CharliePlex FeatherWing hack


Adafruit makes these neat "CharlieWing" displays that allow you to control a 15x7 LED matrix using the I2C bus. I2C uses two signal wires (called SDA and SCL, for Serial DAta and Serial CLock), and can connect multiple devices as long as they have different addresses.

I noticed that the bigger brother of this device, with a whopping 144 LEDs, could be configured for 4 different I2C addresses, while this one could only be configured for 2.

Or could it?

read more…

17 July 2020, 21:37 UTC

Minimal Time-Zone Handling for CircuitPython


For my clock, I want automatic handling of Daylight Saving Time. However, CircuitPython doesn't build in any distinction between local and UTC time, and fitting in the entire Python3 datetime module or an Olson time zone database is simply not going to happen. What can we do that is simple enough to fit, but can represent the reality of timezones where I live?

read more…

9 July 2020, 17:55 UTC

Raspberry Pi Gross Hacks

16 June 2020, 14:04 UTC

Black Lives Matter

19 March 2020, 19:41 UTC

Updates

All older entries
Website Copyright © 2004-2018 Jeff Epler