Square Counting

Design a hardware module for the Square Counting problem.

Given an r x c grid of unit cells, count how many axis-aligned squares of any size can be formed.

Hardware I/O Encoding

• r is a scalar unsigned 32-bit integer
• c is a scalar unsigned 32-bit integer
• the output is one unsigned 64-bit integer
• the output value is the total number of squares in the grid

Examples

Example 1

• input r = 1, c = 1
• output: 1

There is exactly one 1 x 1 square.

Example 2

• input r = 2, c = 3
• output: 8

There are six 1 x 1 squares and two 2 x 2 squares.

Example 3

• input r = 3, c = 3
• output: 14

This includes nine 1 x 1, four 2 x 2, and one 3 x 3 square.

Source: Google Kick Start 2017 Round A - Square Counting