Tuesday, March 18, 2014

Using the CP/M BDS C Compiler

I'll continue giving more details on the programs I demonstrated in the YouTube video The Briel Altair 8800 Kit, Part 5: Advanced Topics.

This time, the BDS C Compiler.

Go to Leo Zolman's BDS C web page and download the release file bdsc-all.zip.

BDS C comes with extensive documentation in the file bdsc-guide.pdf, but for the purposes of a simple demo, you can do the following. Unzip the file and copy these files to an SD card, and then transfer them to a CP/M drive:

BDSCIO.H C.CCC CC.COM CC2.COM
CLINK.COM DEFF.CRL DEFF2.CRL STDIO.H

The example program TAIL.C used in the demonstration was found here.

Here is an even shorter example C program that I  wrote. I entered it as the filename EX1.C:

/* BDS C example 1 */
#include

main(argc,argv)
char **argv;
{
    int i;

    printf("Example Program 1\n");
    for (i=1; i <=10; i++) {
        printf("%d\n", i);
    }
    return 0;
}

Here is a sample session showing EX1.C and TAIL.C being compiled, linked, and run (commands typed by the user are in bold).

B>dir

B: EX1      C   : NQUEENS  C   : BDSCIO   H   : C        CCC
B: CC       COM : CC2      COM : CLINK    COM : DEFF     CRL
B: DEFF2    CRL : STDIO    H   : TAIL     C

B>cc ex1

BD Software C Compiler v1.60  (part I)
  37K elbowroom
BD Software C Compiler v1.60 (part II)
  34K to spare

B>clink ex1

BD Software C Linker   v1.60

Last code address: 0E8D 
Externals start at 0E8E, occupy 0006 bytes, last byte at 0E93 
Top of memory: E805 
Stack space: D972 
Writing output...
  46K link space remaining

B>ex1

Example Program 1
1
2
3
4
5
6
7
8
9
10

B>cc tail

BD Software C Compiler v1.60  (part I)
  36K elbowroom
BD Software C Compiler v1.60 (part II)
  33K to spare

B>clink tail

BD Software C Linker   v1.60

Last code address: 1402 
Externals start at 1403, occupy 0006 bytes, last byte at 1408 
Top of memory: E805 
Stack space: D3FD 
Writing output...
  44K link space remaining

B>tail -10 tail.c

}
                                


int lastchar(c)
char c;
{
        return (!c) || (c == CPMEOF);
}

B>tail

Usage: tail [-#]

B>dir

B: TAIL     CRL : TAIL     COM : NQUEENS  CRL : NQUEENS  COM
B: EX1      C   : NQUEENS  C   : BDSCIO   H   : C        CCC
B: CC       COM : CC2      COM : CLINK    COM : DEFF     CRL
B: DEFF2    CRL : STDIO    H   : TAIL     C   : EX1      CRL
B: EX1      COM

Finally, here is the N Queens example program shown in the YouTube video. It will take a while to run to completion.   First the source code, followed by example output.

/* Solve the n queens problem */

#include

#define MAX_N 8

int  board[MAX_N*MAX_N];
int tries;
int  solutions;
int  n;
int  nsq;
int cache[MAX_N+1]; /* get some savings by caching last position */

/* display the board */
void print_board()
{
  int i;
  
  printf("+");
  for (i = 0; i < n ; i++)
    printf("---");
  printf("+\n");

  for (i = 0; i < nsq ; i++) {
    if ((i % n) == 0)
      printf("|");
    if (board[i])
      printf(" Q ");
    else
      printf(" . ");
    if (((i+1) % n) == 0)
      printf("|\n");
  }

  printf("+");
  for (i = 0; i < n ; i++)
    printf("---");
  printf("+\n");
}

/* find position of a piece */
int piece(n)
{
  int i;

  /* first try the cache */
  if (board[cache[n]] == n)
    return cache[n];
  
  for (i = 0 ; i < nsq ; i++)
    if (board[i] == n) {
      cache[n] = i; /* cache it for next time */
      return i;
    }
  return -1;
}

/* see if board is a solution */
void check_board()
{
  int i, p, r, c, j;

  /* loop over all pieces */
  for (i = 1 ; i <= n ; i++) {
    p = piece(i);

    /* not a solution if piece in same row */
    r = p / n;
    for (c = 0 ; c < n ; c++) {
      if (board[r*n+c] != 0 && board[r*n+c] != i)
return;
    }

    /* not a solution if piece in same column */
    c = p % n;
    for (r = 0 ; r < n ; r++) {
      if (board[r*n+c] != 0 && board[r*n+c] != i)
return;
    }
    
    /* not a solution if piece in same \ diagonal */
    for (j = -n ; j < n ; j++) {
      r = p / n + j;
      c = p % n + j;
      if ((r >= 0) && (r < n) && (c >= 0) && (c < n) &&
 (board[r*n+c] != 0) && (board[r*n+c] != i))
return;
    }
    /* not a solution if piece in same / diagonal */
    for (j = -n ; j < n ; j++) {
      r = p / n + j;
      c = p % n - j;
      if ((r >= 0) && (r < n) && (c >= 0) && (c < n) &&
 (board[r*n+c] != 0) && (board[r*n+c] != i))
return;
    }
  }
  solutions++;
  print_board();
}

/* move piece p to next position */
int next_pos(p)
{
  int i, t;

  if (p < 1)
    return 0;

  i = piece(p);

  if (i < nsq-n+p-1) {
    board[i] = 0;
    board[i+1] = p;
    return 1;
  } else {
    t = next_pos(p-1);
    board[i] = 0;
    board[piece(p-1)+1] = p;
    return t;
  }
}

/* generate the next possible solution */
int next_board()
{
  return next_pos(n);
}


int main()
{
  int i;

  solutions = 0;
  n = 5;
  nsq = n*n;           /* save n^2 to avoid calculating it again */

  printf("\n\n\n\nSOLVING N QUEENS PROBLEM FOR N = %d\n", n);

  /* clear the board */
  for (i = 0 ; i < nsq ; i++)
    board[i] = 0;

  /* initially place the queens */
  for (i = 0 ; i < n ; i++)
    board[i] = i+1;

  do {
    tries++;
    check_board();
  } while (next_board());
  
  printf("FOUND %d SOLUTIONS AFTER %ld TRIES.\n", solutions, tries);
        
  return 0;
}

B>nqueens

SOLVING N QUEENS PROBLEM FOR N = 5
+---------------+
| Q  .  .  .  . |
| .  .  Q  .  . |
| .  .  .  .  Q |
| .  Q  .  .  . |
| .  .  .  Q  . |
+---------------+
+---------------+
| Q  .  .  .  . |
| .  .  .  Q  . |
| .  Q  .  .  . |
| .  .  .  .  Q |
| .  .  Q  .  . |
+---------------+
+---------------+
| .  Q  .  .  . |
| .  .  .  Q  . |
| Q  .  .  .  . |
| .  .  Q  .  . |
| .  .  .  .  Q |
+---------------+
+---------------+
| .  Q  .  .  . |
| .  .  .  .  Q |
| .  .  Q  .  . |
| Q  .  .  .  . |
| .  .  .  Q  . |
+---------------+
+---------------+
| .  .  Q  .  . |
| Q  .  .  .  . |
| .  .  .  Q  . |
| .  Q  .  .  . |
| .  .  .  .  Q |
+---------------+
+---------------+
| .  .  Q  .  . |
| .  .  .  .  Q |
| .  Q  .  .  . |
| .  .  .  Q  . |
| Q  .  .  .  . |
+---------------+
+---------------+
| .  .  .  Q  . |
| Q  .  .  .  . |
| .  .  Q  .  . |
| .  .  .  .  Q |
| .  Q  .  .  . |
+---------------+
+---------------+
| .  .  .  Q  . |
| .  Q  .  .  . |
| .  .  .  .  Q |
| .  .  Q  .  . |
| Q  .  .  .  . |
+---------------+
+---------------+
| .  .  .  .  Q |
| .  Q  .  .  . |
| .  .  .  Q  . |
| Q  .  .  .  . |
| .  .  Q  .  . |
+---------------+
+---------------+
| .  .  .  .  Q |
| .  .  Q  .  . |
| Q  .  .  .  . |
| .  .  .  Q  . |
| .  Q  .  .  . |
+---------------+
FOUND 10 SOLUTIONS AFTER -12406 TRIES.

B>

2 comments:

Anonymous said...

Hi, Jeff. Thanks for these blogposts about CP/M. I'm running CP/M 2.2. on a platform that never got much coverage: the Z80 co-processor for the Acorn BBC Micro! I'm just starting, but I've managed to use your tutorial here to compile the EX1.C example program using the BDSC160 version of the compiler. Yay! The only thing was that I had to explicitly name stdio.h in the include -- otherwise, it refused to compile. Also, I did have some minor issues with the layout of the output from CC.COM and CLINK.COM because my system has a very non-standard terminal indeed! But it's all good fun and a learning experience! Thanks again.

bn said...

Jeff, Glad to see the BDS C in use after all these years :-) Some of the early efforts (Circa 1980s)to develop efficient code on CP/M and others are legendary - Speaks volumes about Leo - a great software engineer - Definitely not brain damaged ;-) - from Bhaskar N/Atlanta GA - Decn2021,