Day 1 - Calorie Counting
Okay everyone it’s advent of code season, we’re back with another round of Christmas themed programming puzzles, this time helping out some elves on a jungle journey. Let’s get that star fruit. I’ve decided to work on today’s problem in SystemVerilog because… idk… YOLO? Nah, SV is good. And by good, I mean awful, but occasionally a fun exercise; something something thinking outside of the box. I’m not going to preemptively self own by committing to doing the whole calendar in SV, but we’ll see where the spirit of the season takes me.
So, what do we have?
Yadda yadda yadda jungle, yadda yadda supplies, traveling by foot…
One important consideration is food - in particular, the number of Calories each Elf is carrying (your puzzle input).
Mmmmmmm, elf snacks.
The Elves take turns writing down the number of Calories contained by the various meals, snacks, rations, etc. that they’ve brought with them, one item per line.
Seems reasonable.
Each Elf separates their own inventory from the previous Elf’s inventory (if any) by a blank line.
Oh boy, here we go.
For example, suppose the Elves finish writing their items’ Calories and end up with the following list:
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
This list represents the Calories of the food carried by five Elves:
The first Elf is carrying food with 1000, 2000, and 3000 Calories, a total of 6000 Calories.
The second Elf is carrying one food item with 4000 Calories.
The third Elf is carrying food with 5000 and 6000 Calories, a total of 11000 Calories.
The fourth Elf is carrying food with 7000, 8000, and 9000 Calories, a total of 24000 Calories.
The fifth Elf is carrying one food item with 10000 Calories.
Okay cool, read the input file, split on double newlines ‘\n\n’ to get the inventory for a particular elf, split those inventories on newlines again to get the individual items. Solid. This is a straightforward enough ask for a normalish programming language. Doing this in SystemVerilog is, shall we say, less than ideal. So instead of doing that we’re going to… well, let’s come back to that… For now let’s finish figuring out what the heck it is we need to do with these elf snacks.
In case the Elves get hungry and need extra snacks, they need to know which Elf to ask: they’d like to know how many Calories are being carried by the Elf carrying the most Calories. In the example above, this is 24000 (carried by the fourth Elf).
Find the Elf carrying the most Calories. How many total Calories is that Elf carrying?
Sounds good, find the elf with the best goodies and take their snacks return the sum of calories of those snacks. Cool, so we need to sum, or accumulate, the number of calories of the snacks that each elf is holding, and then compare the total calories each elf is holding to find the maximum.
In pseudocode this would be something like:
max_elf_snack_cals = 0
for each elf:
if sum(elf's snack calories) > max_elf_snack_cals then
max_elf_snack_cals = sum(elf's snack calories)
So how does this translate to verilog?
Well, to begin we’ll need something to add up the snacks. In old school verilog this would be a reg, in SV we have logic 32 bits to be precise, so:
logic[31:0] calories_sum = 0;
Great, so now we actually have to sum those calories. We’ll do this in an always block with a vld input signal to indicate that the value on another input holding the current snack calories is legit and that we want to add it to our running total.
logic[31:0] calories_sum = 0;
always_ff @ (posedge clk) begin
if (food_vld) begin
calories_sum <= calories_sum + food_calories;
end
end
Hmm, but we need to clear that when we’re done summing up one elf’s snacks and it’s time to move on to the next elf. We could do a nested if… but those get kinda gross. How bout a case?
logic[31:0] calories_sum = 0;
always_ff @ (posedge clk) begin
case ({store_sum, food_vld})
0: calories_sum <= calories_sum; // do nothing / keep the same value
1: calories_sum <= calories_sum + food_calories;
2: calories_sum <= 0;
3: calories_sum <= 0; // Requested both accumulate and clear, error
endcase
end
Nice, but what the heck is this case doing? Why are store_sum and food_vld in braces, why are you counting from 0 to 3? Where are my elf snacks? I’m hungry.
Okay (here’s my two bits) so I’m treating {store_sum, food_vld} as a two bit signal, with food_vld as the low bit, and store_sum the high. The numbers enumerate the possible values that two bit signal can take, and what should be done in each of those cases. This says:
If food_vld is hot, we add the new calories to our running sum. If we’re storing the sum we clear out our current sum (on the next clock edge). If we try to do both at the same time, I’ve elected to clear the sum, and if neither is requested, keep the same value. Looks pretty good. What if something really crazy happens though? Or what about when we start up? Maybe we need some way to uh, reset, to a good known state.
logic[31:0] calories_sum = 0;
always_ff @ (posedge clk) begin
if (rst) begin
calories_sum <= 0;
end else begin
case ({store_sum, food_vld})
0: calories_sum <= calories_sum; // do nothing / keep the same value
1: calories_sum <= calories_sum + food_calories;
2: calories_sum <= 0;
3: calories_sum <= 0; // Requested both accumulate and clear, error
endcase
end
end
That’s better. At every positive/rising edge of our input clock signal, if there’s a valid food_calories number on our input, add it to our running sum. When we decide to store that sum we clear the running sum. Sweet, we can sum up the values. But where exactly are these values coming from? We’re gonna need some inputs. Now that you mention it, this little code snippet is kind of floating in the ether. Lets put it in a module.
module top
(
input logic clk,
input logic rst,
input logic [31:0] food_calories,
input logic food_vld,
input logic store_sum
);
logic[31:0] calories_sum = 0;
always_ff @ (posedge clk) begin
if (rst) begin
calories_sum <= 0;
end else begin
case ({store_sum, food_vld})
0: calories_sum <= calories_sum; // do nothing / keep the same value
1: calories_sum <= calories_sum + food_calories;
2: calories_sum <= 0;
3: calories_sum <= 0; // Requested both accumulate and clear, error
endcase
end
end
endmodule
Looking good, making sense. Although, right now our store_sum is more of a clear_sum, so perhaps we should actually store the calories_sum somewhere. Let’s add another logic and another always block.
logic[31:0] stored_calories = 0;
always_ff @ (posedge clk) begin
if (rst) begin
stored_calories <= 0;
end else begin
if (store_sum) begin
stored_calories <= calories_sum;
end
end
end
Wait… we’re forgetting something. We’re supposed to store the maximum of the calorie sums. Okay, easy enough.
//logic[31:0] stored_calories = 0;
logic[31:0] calories_max = 0;
always_ff @ (posedge clk) begin
if (rst) begin
calories_max <= 0;
end else begin
if (store_sum) begin
calories_max <= (calories_max > calories_sum) ? calories_max : calories_sum;
end
end
end
Boy do I love a ternary conditional. If our max value is greater than our current sum, keep it; otherwise, overwrite it with the current sum. That’s just about it for part one. We just need to take our calories_max and be able to present it to the outside world, so let’s add some logic to hook it up to an output.
input logic read_max;
output logic max_vld;
output logic [31:0] max_calories_sum;
initial begin
max_vld = 0;
max_calories_sum = 0;
end
always_ff @ (posedge clk) begin
if (rst) begin
max_vld <= 0;
max_calories_sum <= 0;
end else if (read_max) begin
max_vld <= 1;
max_calories_sum <= calories_max;
end
end
Not too shabby. Hmm… There is something a little off though. If we did it this way, then after read_max is raised, we set max_vld high, set max_calories_sum to our calories_max and then we leave it like that. That seems problematic. What if we wanted to check the maximum somewhere in the middle while we’re still processing input. If we did that and then kept feeding in new food values and storing sums our max_vld would stay high, and our max_calories_sum would be the same as when we requested it, and wouldn’t account for any of our new input, which would be bad. Let’s not do that.
always_ff @ (posedge clk) begin
//if (rst) begin
if (rst || food_vld) begin
max_vld <= 0;
max_calories_sum <= 0;
end else if (read_max) begin
max_vld <= 1;
max_calories_sum <= calories_max;
end
end
Now we clear our output max signals as soon as we get a new food vld input. This should be fine. We could also do this as soon as we get a store_sum request, and this is a place where API / protocol decisions would come into play, but I think what we have is good for now.
Here’s everything we have so far. I’ve adjusted it a bit to put the new inputs and outputs up at the top.
module top
(
input logic clk,
input logic rst,
input logic [31:0] food_calories,
input logic food_vld,
input logic store_sum,
input logic read_max,
output logic max_vld,
output logic [31:0] max_calories_sum
);
logic[31:0] calories_sum = 0;
always_ff @ (posedge clk) begin
if (rst) begin
calories_sum <= 0;
end else begin
case ({store_sum, food_vld})
0: calories_sum <= calories_sum; // do nothing / keep the same value
1: calories_sum <= calories_sum + food_calories;
2: calories_sum <= 0;
3: calories_sum <= 0; // Requested both accumulate and clear, error
endcase
end
end
logic[31:0] calories_max = 0;
always_ff @ (posedge clk) begin
if (rst) begin
calories_max <= 0;
end else begin
if (store_sum) begin
calories_max <= (calories_max > calories_sum) ? calories_max : calories_sum;
end
end
end
initial begin
max_vld = 0;
max_calories_sum = 0;
end
always_ff @ (posedge clk) begin
if (rst || food_vld) begin
max_vld <= 0;
max_calories_sum <= 0;
end else if (read_max) begin
max_vld <= 1;
max_calories_sum <= calories_max;
end
end
endmodule
Nice, we have a 100% correct, first go, definitely gonna work solution.
Right……
So uh, how do we drive this thing?
Find out next time on. Parallel Elves