A Recursive Scan
The depth first tree search described above would normally be implemented most easily using recursion. While recursion is often considered difficult when it fits in with the nature of the problem it is often the easiest way to work.
A simple, but not quite complete, recursive algorithm for a depth first search described above is relatively easy to construct.
If you don't follow how it works then you can just use it but it is worth trying to understand as it is a really good example of how recursion can make things simpler.
The serial numbers of the devices found will be stored in an array of 64 bit integers:
int oneWireScan(uint8_t pin, uint64_t serial[]) {
We need two static variables to record a global state - bitcount records how deep in the tree we currently are and deviceCount records how many devices we have found so far:
static int bitcount = 0; static int deviceCount = 0;
Notice that static variables are strange in that they are shared between all invocations of a function and they are only initialized once when the program starts - they are allocated on the heap not the stack.
The way to think about oneWireScan and how to think about it if you were writing it from scratch is that calling it will process the bit indicated by the current value of bitcount. As only as you increment bitcount before you call oneWireScan it will process all of the bits down to 63 by repeatedly calling itself to process the next bit.
Next we need to write starting and ending conditions. This is fairly usual with recursion. If the bitcount is greater than 63 then we have a full serial number and can move the deviceCount on by one and zero the bitcount.
if (bitcount > 63) {
bitcount = 0;
deviceCount++;
return deviceCount;
}
Similarly if the bitcount is zero we need to start a traverse of the tree by sending a presence pulse, and then a search command. If there are no devices on the bus then we set bitcount to zero and return as there is nothing to do.
if (bitcount == 0) {
if (presence(pin) == 1) {
bitcount = 0;
return deviceCount;
}
deviceCount = 0;
serial[deviceCount] = 0;
writeByte(pin, 0xF0);
};
Now we are ready read the first or next bit, it doesn't really make a lot of difference to what we have to do.
int b1 = readBit(pin);
int b2 = readBit(pin);
What we have to do does, however depend on b1 and b2. The two simplest conditions are if there are no conflicts on the bus and we simply need to set a zero or a one:
if (b1 == 0 && b2 == 1) {
serial[deviceCount] >>= 1;
writeBit(pin, 0);
bitcount++;
oneWireScan(pin, serial);
};
if (b1 == 1 && b2 == 0) {
serial[deviceCount] >>= 1;
serial[deviceCount] |= 0x8000000000000000LL;
writeBit(pin, 1);
bitcount++;
oneWireScan(pin, serial);
};
We either shift a zero or a one into the serial number we are building up and then write a zero or a one to keep all of the slaves in the scan. Finally, and this is where the recursion comes in, we increment the bitcount and call onWireScan again to process the next bit. This is the part that worries most programmers but as long as you understand that we get a complete new version of oneWireScan and it processes the next bit just like the previous bit then it all works.
If we get b1 and b2 equal to one then we have an error condition and this terminates the processing of the next bit:
if (b1 == 1 && b2 == 1) {
bitcount = 0;
return deviceCount;
};
Notice that you have to set bitcount back to zero otherwise it will be wrong the next time you call the function.
The most difficult of the conditions to deal with is when there is a collision because you have to explore both branches of the tree. Using recursion however this is fairly easy:
if (b1 == 0 && b2 == 0) {
serial[deviceCount] >>= 1;
writeBit(pin, 0);
bitcount++;
oneWireScan(pin, serial);
serial[deviceCount] >>= 1;
serial[deviceCount] |= 0x8000000000000000LL;
writeBit(pin, 1);
bitcount++;
oneWireScan(pin, serial); };
return deviceCount;
}
All that happens here is that first we record a zero in the serial number and send a zero to turn off all the devices with a one in this position. Next we call oneWireScan again to complete this version of the serial number. When this returns we have the completed 64 bit serial number and deviceCount has been incremented. All we have to do next is follow the other branch - record a on in the serial number write a one to turn off all of the devices with zero in this position, we already have them in the array, and then call onWireScan to find the remaining bits.
That finishes the function and the final instruction is:
return deviceCount;
}
If you try this out you will find it doesn't work.
The reason is very simple. In the conflict handling part of the function it is assumed that when the first call to oneWireScan returns the function is exactly where it was before the call i.e. the same bit position and ready to continue down the new branch of the tree. This is true as far as the function is concerned but the devices on the bus have physically moved on and are no longer a the same bit position. In fact the scan has completed we are at bit 63 and we need to start a new scan. Not only do we need to start a new scan we need to restore the hardware to the position it was in just before the call to oneWireScan.
This is the reason that most programmers don't implement the scan as a recursive function - the function is recursive but the hardware isn't. If we had a hardware stack we could simply push the state just before the call and then pop it when the call returns. We don't have a hardware stack but it is very easy to restore the state of the hardware.
In fact the only thing we need to record is the current bitposition in a local rather than static variable:
int bitposition = bitcount;
bitcount++;
oneWireScan(pin, serial);
Now when the onWireScan returns bitposition holds the number of the bit that it was working on before the call.
We can now restore the bitcount and start a completely new scan:
bitcount = bitposition;
if (presence(pin) == 1){
bitposition=0;
return 0;
}
writeByte(pin, 0xF0);
Now we are actually at bit zero of the scan but we want to be at the current bitposition. If you think about it the bits of the next serial number up to bitposition are going to be the same as the previously retrieved number - they are only different after this point. So we can retrieve the first part of the serial number from the previous serial number. The only difference is that the last bit that we want isn't going to be a zero it now needs to be a one to take us down the next branch of the tree. We can do this in one go:
uint64_t temp = serial[deviceCount - 1] | (0x1LL << (bitcount));
Now we need to walk the hardware though all of the bits in temp from bit zero to bitcount:
int i;
uint64_t bit;
for (i = 0; i < bitcount+1; i++) {
bit = temp & 0x01LL;
temp >>= 1;
b1 = readBit(pin);
b2 = readBit(pin);
writeBit(pin, bit);
serial[deviceCount] >>= 1;
serial[deviceCount] |= (bit << 63);
}
We now have the hardware restored to the state just before the first call to oneWireScan and we have sent a one in place of the zero for the current bit. We can now call oneWireScan again to explore the alternative branch of the tree:
bitcount++;
oneWireScan(pin, serial);
};
That's all we need - a recursive scan of the 1-wire bus.
