Section: Bit Manipulations - Create Lookup Table

Section: Bit Manipulations - Create Lookup Table#

Adapted from: gjbex/Fortran-MOOC

This program demonstrates bit manipulations using Fortran.

Code Analysis by ChatGPT 4o: create_lookup_table.f90#

The provided Fortran program create_lookup_table performs the following tasks:

Overview#

This program creates a lookup table of integers (256 entries) and writes it to a file specified as a command-line argument. The table is constructed to store the number of 1s in the binary representation of integers from 0 to 255. The program outputs the data into a formatted text file in groups of 16 integers per line.

Key Components#

1. Program Initialization#

  • The use, intrinsic :: iso_fortran_env imports constants such as error_unit, which is used for error reporting.

  • lookup_table is an integer array of size 256 to hold the lookup table values.

  • file_name is a character string to store the file name provided by the user.

  • Various local variables (unit_nr, istat, msg, etc.) are used for file operations.

2. Command-Line Argument Handling#

  • The program expects one command-line argument: the output file name.

  • It checks if exactly one argument is provided using command_argument_count().

  • If the argument count is incorrect, it writes an error message to the error_unit and stops execution.

3. Lookup Table Initialization#

  • A contains section defines the function init_lookup_table, which calculates the lookup table values.

  • Each entry in lookup_table(i) represents the count of 1s in the binary representation of the integer i.

    • This is computed using the formula: $\( \text{lookup\_table}(i) = \text{AND}(i, 1) + \text{lookup\_table}(i/2) \)$

    • The formula exploits the fact that i/2 shifts i one bit to the right, and AND(i, 1) extracts the least significant bit of i.

4. File Handling#

  • The file is opened using open, with the newunit option to get a unique file unit and status='replace' to overwrite the file if it exists.

  • If an error occurs during file opening, the program writes the error message stored in iomsg to the error_unit.

5. Writing the Lookup Table#

  • The program writes the lookup table to the file in a formatted manner:

    • It outputs 16 numbers per line for the first 15 lines, each separated by commas.

    • The 16th line writes the remaining 15 numbers (from index 240 to 255) and a final number (lookup_table(256)).

  • Each line is indented for readability, and Fortran’s continuation character (&) is used for lines longer than the maximum line length.

6. Cleanup#

  • After writing the data, the file is closed.

Detailed Explanation of Functions and Constructs#

init_lookup_table#

This function initializes the lookup table by calculating the number of 1s in the binary representation of integers from 0 to 255:

  1. lookup_table(0) = 0: The number 0 has no 1s in its binary representation.

  2. For each i from 1 to 255, the formula computes the count of 1s as:

    • and(i, 1): Checks if the least significant bit of i is 1.

    • lookup_table(i/2): Uses the precomputed value of i/2 to avoid redundant calculations.

Writing to File#

The formatted output is controlled by write statements:

  • The main loop iterates over groups of 16 integers and formats them as:

            0, 1, 1, 2, 1, 2, 2, 3, ...

  • The last line is handled separately to avoid trailing commas.

Sample Output#

Assume the lookup table for the first 16 integers is as follows:

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4

The file might look like this:

        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, &
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, &
        ...

Error Handling#

  • If no file name is provided, an error message is printed:

    error: expecting file name as argument

  • If file operations fail, an error message is printed with details of the issue.

Use Cases#

This program is useful for:

  1. Generating lookup tables for bit-counting applications.

  2. Demonstrating efficient table initialization using recursion.

  3. Creating formatted output for use in other programs or as human-readable data.

Program Code#

program create_lookup_table
    use, intrinsic :: iso_fortran_env, only : error_unit
    implicit none
    integer, dimension(256) :: lookup_table
    character(len=1024) :: file_name, msg
    integer :: i, unit_nr, istat

    lookup_table = init_lookup_table()
    if (command_argument_count() /= 1) then
        write (unit=error_unit, fmt='(A)') 'error: expacting file name as argument'
        stop 1
    end if
    call get_command_argument(1, file_name)
    open (newunit=unit_nr, file=trim(file_name), status='replace', &
        access='sequential', form='formatted', iostat=istat, iomsg=msg)
    if (istat /= 0) then
        write (unit=error_unit, fmt='(2A)') 'error: ', trim(msg)
        stop 1
    end if
    do i = 1, 15
        write (unit=unit_nr, fmt='("        ", 16(I3, ","), " &")') &
            lookup_table((i - 1)*16 + 1:i*16) 
    end do
    write (unit=unit_nr, fmt='("        ", 15(I3, ","))', advance='no') &
                lookup_table(15*16 + 1:16*16 - 1) 
    write (unit=unit_nr, fmt='(I3, " &")') lookup_table(256)
    close (unit=unit_nr)

contains

    function init_lookup_table() result(lookup_table)
        implicit none
        integer, dimension(0:255) :: lookup_table
        integer :: i

        lookup_table(0) = 0
        do i = 1, 255
            lookup_table(i) = and(i, 1) + lookup_table(i/2)
        end do
    end function init_lookup_table

end program create_lookup_table

The above program is compiled and run using Fortran Package Manager (fpm). The following FPM configuration file (fpm.toml) was used:

name = "Section_Bit_Manipulations_Create_Lookup_Table"

[build]
auto-executables = true
auto-tests = true
auto-examples = true

[install]
library = false

[[executable]]
name="Section_Bit_Manipulations_Create_Lookup_Table"
source-dir="app"
main="section_bit_manipulations_create_lookup_table.f90"

Build the Program using FPM (Fortran Package Manager)#

import os
root_dir = ""
root_dir = os.getcwd()

code_dir = root_dir + "/" + "Fortran_Code/Section_Bit_Manipulations_Create_Lookup_Table"

os.chdir(code_dir)

build_status = os.system("fpm build 2>/dev/null")

Run the Program using FPM (Fortran Package Manager)#

The program is run and the output is saved into a file named ‘data.dat

exec_status = \
    os.system("fpm run -- lookup_table.dat 2>/dev/null")

Display the Output File#

exec_status = \
    os.system("cat lookup_table.dat")

          0,  1,  1,  2,  1,  2,  2,  3,  1,  2,  2,  3,  2,  3,  3,  4, &
          1,  2,  2,  3,  2,  3,  3,  4,  2,  3,  3,  4,  3,  4,  4,  5, &
          1,  2,  2,  3,  2,  3,  3,  4,  2,  3,  3,  4,  3,  4,  4,  5, &
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6, &
          1,  2,  2,  3,  2,  3,  3,  4,  2,  3,  3,  4,  3,  4,  4,  5, &
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6, &
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6, &
          3,  4,  4,  5,  4,  5,  5,  6,  4,  5,  5,  6,  5,  6,  6,  7, &
          1,  2,  2,  3,  2,  3,  3,  4,  2,  3,  3,  4,  3,  4,  4,  5, &
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6, &
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6, &
          3,  4,  4,  5,  4,  5,  5,  6,  4,  5,  5,  6,  5,  6,  6,  7, &
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6, &
          3,  4,  4,  5,  4,  5,  5,  6,  4,  5,  5,  6,  5,  6,  6,  7, &
          3,  4,  4,  5,  4,  5,  5,  6,  4,  5,  5,  6,  5,  6,  6,  7, &
          4,  5,  5,  6,  5,  6,  6,  7,  5,  6,  6,  7,  6,  7,  7,  8 &