home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / demos / audio / bz / bzvalidate.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  31.8 KB  |  1,306 lines
  1. /*
  2.  * Copyright (C) 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /***************************************************************************
  18.  *
  19.  * @(#) - BZ - Multiplayer tank game - Host validation routines.
  20.  *
  21.  *                    Chris Fouts - Silicon Graphics, Inc.
  22.  *                    October, 1991
  23.  **************************************************************************/
  24. #include <stdio.h>
  25. #include <stdarg.h>
  26. #include <malloc.h>
  27. #include <sys/types.h>
  28. #include <sys/socket.h>
  29. #include <netinet/in.h>
  30. #include <netdb.h>
  31. #include <arpa/inet.h>
  32. #include <time.h>
  33.  
  34. #include <X11/Intrinsic.h>
  35.  
  36. #include "bz.h"
  37. #include "bzvalidate.h"
  38. #include "bzbase.h"
  39. #include "framerate.h"
  40.  
  41. #define    MAX_DROPS    2
  42. #define    MAX_QUITS    3
  43. #define    MAX_ACKS    20
  44.  
  45. #define    BZ_STEADY_CENSUS_RATE    400            /* tenths o' seconds */
  46. #define    BZ_UNSTEADY_CENSUS_RATE     40            /* tenths o' seconds */
  47. #define BZ_NEW_DEADLINE_TIME     50            /* seconds */
  48. #define BZ_OLD_DEADLINE_TIME    120            /* seconds */
  49. #define    BZ_WEEDING_TIME             15            /* seconds */
  50. #define    BZ_DROPPING_DELTA        -30            /* seconds */
  51.  
  52. #define BZ_VALID_UNKNOWN        0
  53. #define BZ_VALID                1
  54. #define BZ_INVALID                2
  55. #define BZ_DROPPED                3
  56. #define BZ_VALID_QUIT            4
  57.  
  58. struct bz_host {
  59.     long            id ;
  60.     short            agrees ;
  61.     short            drops ;
  62.     short            quits ;
  63.     short            acks ;
  64.     short            valid ;
  65.     short            last_valid ;
  66.     struct bz_host    *next ;
  67.     } ;
  68.  
  69. struct bz_census {
  70.     struct BzCensus        census ;
  71.     struct bz_census    *next ;
  72.     } ;
  73.  
  74. /* BEGIN PROTOTYPES -S bzvalidate.c */
  75. static struct bz_host  *add_host( long host_id ) ;
  76. static int              compare_census( struct BzCensus *input ) ;
  77. static void             copybytes( void *src, void *dst, long n ) ;
  78. static void             do_weeding( void ) ;
  79. static struct bz_host  *find_host( long host_id ) ;
  80. static int              find_host_in_my_census_list( long id ) ;
  81. static void             generate_census_checksum( void ) ;
  82. static void             list_hosts( void ) ;
  83. static void             reset_deadlines( int except ) ;
  84. static void             show_host_validity( struct bz_host *host ) ;
  85. /* END PROTOTYPES -S bzvalidate.c */
  86.  
  87. static struct bz_host    *first_host = NULL ;
  88. static unsigned short    game_key = 0 ;
  89. static struct timeval    last_census_sent ;
  90. static long                time_between_census_posts = 0 ;
  91. static Boolean            need_to_send_census ;
  92. static Boolean            need_to_do_weeding = FALSE ;
  93. extern struct timeval    current_time ;
  94. extern struct timeval    start_up_time ;
  95. static struct timeval    weed_time ;
  96. static struct bz_census    my_census ;
  97. extern struct BzMember    player[] ;
  98. extern struct timeval    deadline[] ;
  99. extern unsigned int        number_players ;
  100.  
  101.  
  102.  
  103. /*------------------------------------------------------------------------------
  104.  * Find a host within the host list.
  105.  *----------------------------------------------------------------------------*/
  106. static struct bz_host *find_host(
  107.     long host_id
  108.     )
  109. {
  110.     struct bz_host    *host = first_host ;
  111.  
  112.     while( host != NULL ) {
  113.         if( host->id == host_id ) {
  114.             return( host ) ;
  115.             }
  116.         else {
  117.             host = host->next ;
  118.             }
  119.         }
  120.  
  121.     return( host ) ;
  122. }
  123.  
  124.  
  125.  
  126. /*------------------------------------------------------------------------------
  127.  * Add a host to the host list.
  128.  *----------------------------------------------------------------------------*/
  129. static struct bz_host *add_host(
  130.     long host_id
  131.     )
  132. {
  133.     struct bz_host    *host = first_host ;
  134.     struct bz_host    *prev = NULL ;
  135.  
  136.     while( host != NULL ) {
  137.         prev = host ;
  138.         host = host->next ;
  139.         }
  140.  
  141.     if( ( host = (struct bz_host *)malloc( sizeof( struct bz_host ) ) ) !=
  142.         NULL ) {
  143.         host->id = host_id ;
  144.         host->agrees = 0 ;
  145.         host->drops = 0 ;
  146.         host->quits = 0 ;
  147.         host->acks = 0 ;
  148.         host->valid = BZ_VALID_UNKNOWN ;
  149.         host->last_valid = BZ_VALID_UNKNOWN ;
  150.         host->next = NULL ;
  151.         if( first_host == NULL ) {
  152.             first_host = host ;
  153.             }
  154.         dprintf( "%s: started receiving from %s\n",
  155.                   print_time(), host_name_from_id( host_id ) ) ;
  156.         }
  157.  
  158.     if( prev != NULL ) {
  159.         prev->next = host ;
  160.         }
  161.  
  162.     return( host ) ;
  163. }
  164.  
  165.  
  166.  
  167. /*------------------------------------------------------------------------------
  168.  * Remove a host from the host list.
  169.  *----------------------------------------------------------------------------*/
  170. void remove_host(
  171.     long host_id
  172.     )
  173. {
  174.     struct bz_host    *host = first_host ;
  175.     struct bz_host    *prev = NULL ;
  176.  
  177.     while( host != NULL && host->id != host_id ) {
  178.         prev = host ;
  179.         host = host->next ;
  180.         }
  181.  
  182.     if( host == NULL )
  183.         return ;
  184.  
  185.     if( host->id == host_id ) {
  186.         /*
  187.          * If prev == NULL, this means we're removing the first host.
  188.          * Set the first_host to point to the next host.
  189.          */
  190.         if( prev == NULL ) {
  191.             first_host = host->next ;
  192.             }
  193.         /*
  194.          * We're past the first host, so link up the previous one to
  195.          * the next one.
  196.          */
  197.         else {
  198.             prev->next = host->next ;
  199.             }
  200.         free( host ) ;
  201.         }
  202.  
  203. #if defined( NETDEBUGGER )
  204.     list_hosts() ;
  205. #endif /* defined( NETDEBUGGER ) */
  206.  
  207.     return ;
  208. }
  209.  
  210.  
  211.  
  212. /*------------------------------------------------------------------------------
  213.  * Returns non-zero if the maximum number of acknowledgement packets have
  214.  * not been sent.
  215.  *----------------------------------------------------------------------------*/
  216. int should_acknowledge(
  217.     long host_id,
  218.     unsigned short key
  219.     )
  220. {
  221.     struct bz_host    *host ;
  222.     int                st ;
  223.  
  224.     if( key != game_key ) {
  225.         return( 0 ) ;
  226.         }
  227.  
  228.     if( ( host = find_host( host_id ) ) == NULL ) {
  229.         if( ( host = add_host( host_id ) ) == NULL ) {
  230.             perror( "should_acknowledge" ) ;
  231.             end_program( 1 ) ;
  232.             }
  233.         }
  234.  
  235.     if( host->acks < MAX_ACKS && host->valid == BZ_VALID_UNKNOWN ) {
  236.         host->acks++ ;
  237.         st = 1 ;
  238.         if( host->acks == 1 ) {
  239.             dprintf( "%s: should acknowledge %s.\n", print_time(),
  240.                 host_name_from_id( host_id ) );
  241.             }
  242.         }
  243.     else {
  244.         st = 0 ;
  245.         }
  246.  
  247.  
  248.     return( st ) ;
  249. }
  250.  
  251.  
  252.  
  253. /*------------------------------------------------------------------------------
  254.  * Called *only* when an ACKNOWLEDGEMENT packet is received (or in view-only
  255.  * mode).
  256.  *---------------------------------------------------------------------------*/
  257. int valid_keyed_host(
  258.     long host_id,
  259.     unsigned short key
  260.     )
  261. {
  262.     struct bz_host    *host ;
  263.  
  264.     if( key != game_key ) {
  265.         return( 0 ) ;
  266.         }
  267.  
  268.     if( ( host = find_host( host_id ) ) == NULL ) {
  269.         if( ( host = add_host( host_id ) ) == NULL ) {
  270.             perror( "valid_keyed_host" ) ;
  271.             end_program( 1 ) ;
  272.             }
  273.         }
  274.  
  275.     if( host->valid == BZ_VALID_UNKNOWN ) {
  276.         host->valid = BZ_VALID ;
  277.         dprintf( "%s: acknowledged by %s\n",
  278.                   print_time(), host_name_from_id( host_id ) ) ;
  279.         }
  280.     /*
  281.      * If host had dropped me, it's now receiving my packets, so send an
  282.      * ACK packet so it will know I see it and add me to its game.
  283.      */
  284.     else if( host->valid == BZ_DROPPED ) {
  285.         host->valid = BZ_VALID ;
  286.         send_acknowledgement( host_id ) ;
  287.         dprintf( "%s: re-acknowledged by %s (had dropped me)\n",
  288.                   print_time(), host_name_from_id( host_id ) ) ;
  289.         }
  290.  
  291.     return( host->valid == BZ_VALID ) ;
  292. }
  293.  
  294.  
  295.  
  296. /*------------------------------------------------------------------------------
  297.  * Returns TRUE if a host is valid.
  298.  *----------------------------------------------------------------------------*/
  299. int valid_host(
  300.     long host_id
  301.     )
  302. {
  303.     struct bz_host    *host ;
  304.  
  305.     if( ( host = find_host( host_id ) ) == NULL ) {
  306.         return( 0 ) ;
  307.         }
  308.  
  309.     /*
  310.      * If host had quit, he has started back up again, so reset its status.
  311.      */
  312.     if( host->valid == BZ_VALID_QUIT ) {
  313.         host->valid = BZ_VALID_UNKNOWN ;
  314.         dprintf( "%s: receiving from %s again (had quit)\n",
  315.                   print_time(), host_name_from_id( host_id ) ) ;
  316.         }
  317.  
  318.     return( host->valid == BZ_VALID ) ;
  319. }
  320.  
  321.  
  322.  
  323. /*------------------------------------------------------------------------------
  324.  * Note that a invalid host quit.
  325.  *---------------------------------------------------------------------------*/
  326. void quit_host(
  327.     long host_id
  328.     )
  329. {
  330.     struct bz_host    *host ;
  331.     struct BzAck            invalid ;
  332.  
  333.     if( ( host = find_host( host_id ) ) == NULL ) {
  334.         return ;
  335.         }
  336.  
  337.     if( host->valid != BZ_VALID_QUIT && host->quits < MAX_QUITS ) {
  338.         host->quits += 1 ;
  339.         host->last_valid = host->valid ;
  340.         host->valid = BZ_VALID_QUIT ;
  341.         host->acks = 0 ;
  342.         dprintf( "%s: %s quit\n", print_time(), host_name_from_id( host_id ) ) ;
  343.         }
  344. }
  345.  
  346.  
  347.  
  348. /*------------------------------------------------------------------------------
  349.  * Drop a host when I haven't received any packets in a while from it.
  350.  *---------------------------------------------------------------------------*/
  351. void drop_host(
  352.     long host_id
  353.     )
  354. {
  355.     struct bz_host    *host ;
  356.     struct BzAck            invalid ;
  357.  
  358.     if( ( host = find_host( host_id ) ) == NULL ) {
  359.         return ;
  360.         }
  361.     host->drops += 1 ;
  362.  
  363.     if( host->drops > MAX_DROPS ) {
  364.         invalidate_host( host_id ) ;
  365.         }
  366.     else {
  367.         /*
  368.          * Notify host of being dropped.
  369.          */
  370.         invalid.bz_id = BZDROP ;
  371.         invalid.id = player[SELF].id ;
  372.         invalid.ack_id = host_id ;
  373.         invalid.key = game_key ;
  374.         send_out( &invalid, sizeof( invalid ) ) ;
  375. #if defined( NETDEBUGGER )
  376.         post_new_message( 0, 0, "sent drop packet to %c", 'a' + host_id ) ;
  377. #endif /* defined( NETDEBUGGER ) */
  378.  
  379.         /*
  380.          * Reset the host so that when I start receiving packets from it
  381.          * again, I'll acknowledge it.
  382.          */
  383.         host->valid = BZ_VALID_UNKNOWN ;
  384.         host->acks = 0 ;
  385.         dprintf( "%s: dropping %s from game (stopped getting packets)\n",
  386.                   print_time(), host_name_from_id( host_id ) ) ;
  387.         }
  388. }
  389.  
  390.  
  391.  
  392. /*------------------------------------------------------------------------------
  393.  * I've been dropped by a host, so indicate status with that host so that I
  394.  * can know when it starts receiving me again.
  395.  *---------------------------------------------------------------------------*/
  396. void dropped_by_host(
  397.     long host_id
  398.     )
  399. {
  400.     struct bz_host            *host ;
  401.  
  402.     if( ( host = find_host( host_id ) ) != NULL ) {
  403.         host->valid = BZ_DROPPED ;
  404.         dprintf( "%s: removing %s from game (dropped by him)\n",
  405.                   print_time(), host_name_from_id( host_id ) ) ;
  406.         }
  407. }
  408.  
  409.  
  410.  
  411. /*------------------------------------------------------------------------------
  412.  * Invalidate a host.  This is permanent.  Will ignore all future packets
  413.  * from this host (until it quits).
  414.  *---------------------------------------------------------------------------*/
  415. void invalidate_host(
  416.     long host_id
  417.     )
  418. {
  419.     int                        i ;
  420.     int                        j ;
  421.     struct bz_host            *host ;
  422.     struct BzAck            invalid ;
  423.     struct bz_census        *cen ;
  424.  
  425.     if( ( host = find_host( host_id ) ) != NULL ) {
  426.         host->valid = BZ_INVALID ;
  427.  
  428.         /*
  429.          * Notify host of being invalidated.
  430.          */
  431.         invalid.bz_id = BZINVALIDATE ;
  432.         invalid.id = player[SELF].id ;
  433.         invalid.ack_id = host_id ;
  434.         invalid.key = game_key ;
  435.         send_out( &invalid, sizeof( invalid ) ) ;
  436.         if( ( cen = find_host_census( host_id ) ) != NULL ) {
  437.             dprintf( "%s: %s invalidated --\n",
  438.                      print_time(), host_name_from_id( host_id ) ) ;
  439.             dprintf( "\tHe sees %ld hosts while you see %ld.\n",
  440.                      cen->census.n_players, my_census.census.n_players ) ;
  441.             dprintf( "\tThe following hosts were seen by him:\n" ) ;
  442.             for( i = 0 ; i < cen->census.n_players ; i++ ) {
  443.                 if( cen->census.list[i] == player[SELF].id ) {
  444.                     dprintf( "\t\t%s (valid - self)\n",
  445.                             host_name_from_id( cen->census.list[i] ) ) ;
  446.                     }
  447.                 else {
  448.                     host = find_host( cen->census.list[i] ) ;
  449.                     if( host == NULL ) {
  450.                         dprintf( "\t\t%s (do not see)\n",
  451.                                 host_name_from_id( cen->census.list[i] ) ) ;
  452.                         }
  453.                     else {
  454.                         show_host_validity( host ) ;
  455.                         }
  456.                     }
  457.                 }
  458.             dprintf( "\tThe following hosts were seen by you but "
  459.                                 "not validated by him:\n" ) ;
  460.  
  461.             j = 0 ;
  462.             for( i = 0 ; i < my_census.census.n_players ; i++ ) {
  463.                 while( j < cen->census.n_players &&
  464.                        my_census.census.list[i] > cen->census.list[j] ) {
  465.                     j++ ;
  466.                     }
  467.                 if( j < cen->census.n_players &&
  468.                     my_census.census.list[i] == cen->census.list[j] ) {
  469.                     j++ ;
  470.                     }
  471.                 else if( my_census.census.list[i] != player[SELF].id ) {
  472.                     dprintf( "\t\t%s\n",
  473.                             host_name_from_id( my_census.census.list[i] ) ) ;
  474.                     }
  475.                 }
  476.             dprintf( "end list for %s\n\n", host_name_from_id( host_id ) ) ;
  477.             }
  478.         }
  479. }
  480.  
  481.  
  482.  
  483. /*------------------------------------------------------------------------------
  484.  * Print out the valid of a host.
  485.  *----------------------------------------------------------------------------*/
  486. static void show_host_validity(
  487.     struct bz_host *host
  488.     )
  489. {
  490.  
  491.     if( host->valid == BZ_INVALID ) {
  492.         dprintf( "\t\t%s (invalidated)\n",
  493.                 host_name_from_id( host->id ) ) ;
  494.         }
  495.     else if( host->valid == BZ_VALID_UNKNOWN ) {
  496.         if( host->drops ) {
  497.             dprintf( "\t\t%s (lost communication from)\n",
  498.                     host_name_from_id( host->id ) ) ;
  499.             }
  500.         else {
  501.             dprintf( "\t\t%s (does not see me)\n",
  502.                     host_name_from_id( host->id ) ) ;
  503.             }
  504.         }
  505.     else if( host->valid == BZ_VALID_QUIT ) {
  506.         if( host->last_valid == BZ_VALID_QUIT ) {
  507.             dprintf( "\t\t%s (thought had quit)\n",
  508.                     host_name_from_id( host->id ) ) ;
  509.             }
  510.         else {
  511.             host->valid = host->last_valid ;
  512.             show_host_validity( host ) ;
  513.             host->valid = BZ_VALID_QUIT ;
  514.             }
  515.         }
  516.     else {
  517.         dprintf( "\t\t%s (valid)\n",
  518.                 host_name_from_id( host->id ) ) ;
  519.         }
  520. }
  521.  
  522.  
  523.  
  524. /*------------------------------------------------------------------------------
  525.  * Register the game's key code.
  526.  *----------------------------------------------------------------------------*/
  527. void register_key(
  528.     unsigned short key
  529.     )
  530. {
  531.     game_key = key ;
  532. }
  533.  
  534.  
  535.  
  536. /*------------------------------------------------------------------------------
  537.  * Generate the census checksum (both xor and summation) from the list of
  538.  * hostid's in the census host list.
  539.  *----------------------------------------------------------------------------*/
  540. static void generate_census_checksum( void )
  541. {
  542.     int    i ;
  543.  
  544.     my_census.census.chksum = 0 ;
  545.     my_census.census.chkxor = 0 ;
  546.     for( i = 0 ; i < my_census.census.n_players ; i++ ) {
  547.         my_census.census.chksum = ( my_census.census.chksum +
  548.                     ( my_census.census.list[i] & 0x3fffffff ) ) & 0x3fffffff ;
  549.         my_census.census.chkxor ^= my_census.census.list[i] ;
  550.         }
  551. }
  552.  
  553.  
  554.  
  555. /*------------------------------------------------------------------------------
  556.  * Initialize the internal census packet.
  557.  *----------------------------------------------------------------------------*/
  558. void init_census_packet(
  559.     long id
  560.     )
  561. {
  562.     my_census.census.bz_id     = BZCENSUS ;
  563.     my_census.census.id        = id ;
  564.     my_census.census.n_players = 1 ;
  565.     my_census.census.list[0]   = id ;
  566.     my_census.next               = NULL ;
  567.     copy_time( &last_census_sent, ¤t_time ) ;
  568.  
  569.     set_time( &weed_time, ¤t_time, BZ_WEEDING_TIME, 0 ) ;
  570.     need_to_do_weeding = FALSE ;
  571.  
  572.     generate_census_checksum() ;
  573. }
  574.  
  575.  
  576.  
  577. /*------------------------------------------------------------------------------
  578.  * Move bytes from one source to another, allowing for overlap
  579.  *----------------------------------------------------------------------------*/
  580. static void copybytes(
  581.     void *src,
  582.     void *dst,
  583.     long n
  584.     )
  585. {
  586.     char    *s ;
  587.     char    *d ;
  588.  
  589.     if( src > dst ) {
  590.         s = (char *)src ;
  591.         d = (char *)dst ;
  592.         while( n-- )
  593.             *(d++) = *(s++) ;
  594.         }
  595.     else {
  596.         s = (char *)src + n ;
  597.         d = (char *)dst + n ;
  598.         while( n-- )
  599.             *(--d) = *(--s) ;
  600.         }
  601. }
  602.  
  603.  
  604.  
  605. /*------------------------------------------------------------------------------
  606.  * Add a host to our census list.
  607.  *----------------------------------------------------------------------------*/
  608. void add_host_to_census(
  609.     long id
  610.     )
  611. {
  612.     int                        n ;
  613.     int                        i ;
  614.     int                        insert_pt ;
  615.     static int                first = 1 ;
  616.     struct bz_census        *next = my_census.next ;
  617.     struct bz_census        *prev = &my_census ;
  618.  
  619.     if( find_host_in_my_census_list( id ) != -1 ) {
  620.         return ;
  621.         }
  622.  
  623.     if( ( i = find_player( id ) ) == -1 ) {
  624.         return ;
  625.         }
  626.  
  627.     n = (my_census.census.n_players)++ ;
  628.  
  629.     while( next ) {
  630.         prev = next ;
  631.         next = next->next ;
  632.         }
  633.  
  634.     if( ( next = calloc( 1, sizeof( struct bz_census ) ) ) == NULL ) {
  635.         perror( "add_host_to_census" ) ;
  636.         end_program( 1 ) ;
  637.         }
  638.  
  639.     prev->next = next ;
  640.  
  641.     next->census.id = id ;
  642.     next->census.n_players = 1 ;
  643.     next->census.chksum    = id ;
  644.     next->census.chkxor    = id ;
  645.  
  646.     insert_pt = n ;
  647.     while( insert_pt && my_census.census.list[insert_pt-1] > id )
  648.         insert_pt-- ;
  649.  
  650.     copybytes( &(my_census.census.list[insert_pt]),
  651.                &(my_census.census.list[insert_pt+1]),
  652.                ( n - insert_pt ) * sizeof( my_census.census.list[0] ) ) ;
  653.  
  654.     my_census.census.list[insert_pt] = id ;
  655.  
  656.     generate_census_checksum() ;
  657.  
  658.     if( !first ) {
  659.         reset_deadlines( i ) ;
  660.         }
  661.     first = 0 ;
  662.  
  663.     set_time( &weed_time, ¤t_time, BZ_WEEDING_TIME, 0 ) ;
  664.     need_to_do_weeding = TRUE ;
  665.  
  666.     set_time( &(deadline[i]), ¤t_time, BZ_NEW_DEADLINE_TIME, 0 ) ;
  667.     dprintf( "%s: added %s to game and census\n", print_time(),
  668.             host_name_from_id( id ) ) ;
  669.  
  670. #if defined( NETDEBUGGER )
  671.     post_new_message( 0, 0, "added host %s to census, deadline = %s",
  672.                         player[i].name,
  673.                         print_time_hundreths( &(deadline[i]) ) ) ;
  674. #endif /* defined( NETDEBUGGER ) */
  675.  
  676.     need_to_send_census = TRUE ;
  677. }
  678.  
  679.  
  680.  
  681. /*------------------------------------------------------------------------------
  682.  * Find a host in the linked list of census packets.
  683.  *----------------------------------------------------------------------------*/
  684. struct bz_census *find_host_census(
  685.     long id
  686.     )
  687. {
  688.     struct bz_census        *next = my_census.next ;
  689.  
  690.     while( next && next->census.id != id ) {
  691.         next = next->next ;
  692.         }
  693.  
  694.     return( next ) ;
  695. }
  696.  
  697.  
  698.  
  699. /*------------------------------------------------------------------------------
  700.  * Remove a host from our census list.
  701.  *----------------------------------------------------------------------------*/
  702. void remove_host_from_census(
  703.     long id
  704.     )
  705. {
  706.     int    n ;
  707.     struct bz_census        *next = my_census.next ;
  708.     struct bz_census        *prev = &my_census ;
  709.  
  710.     n = find_host_in_my_census_list( id ) ;
  711.  
  712.     while( next && next->census.id != id ) {
  713.         prev = next ;
  714.         next = next->next ;
  715.         }
  716.  
  717.     if( n < 0 || next == NULL ) {
  718.         return ;
  719.         }
  720.  
  721.     prev->next = next->next ;
  722.  
  723.     free( next ) ;
  724.  
  725.     my_census.census.n_players-- ;
  726.  
  727.     copybytes( &(my_census.census.list[n+1]), &(my_census.census.list[n]),
  728.         (my_census.census.n_players - n) * sizeof( my_census.census.list[0] ) );
  729.  
  730.     generate_census_checksum() ;
  731.  
  732.     need_to_send_census = TRUE ;
  733. }
  734.  
  735.  
  736.  
  737. /*------------------------------------------------------------------------------
  738.  * Locate a host within our census list.
  739.  *----------------------------------------------------------------------------*/
  740. static int find_host_in_my_census_list(
  741.     long id
  742.     )
  743. {
  744.     int        n ;
  745.     int        lo = 0 ;
  746.     int        hi = my_census.census.n_players - 1 ;
  747.     long    *census_list = my_census.census.list ;
  748.  
  749.     while( 1 ) {
  750.         n = ( lo + hi ) / 2 ;
  751.         if( id == census_list[n] ) {
  752.             return( n ) ;
  753.             }
  754.         else if( id < census_list[n] ) {
  755.             hi = n - 1 ;
  756.             }
  757.         else {
  758.             lo = n + 1 ;
  759.             }
  760.         if( lo > hi ) {
  761.             return( -1 ) ;
  762.             }
  763.         }
  764. }
  765.  
  766.  
  767.  
  768. /*------------------------------------------------------------------------------
  769.  * Compare a census packet with another.
  770.  *----------------------------------------------------------------------------*/
  771. static int compare_census(
  772.     struct BzCensus *input
  773.     )
  774. {
  775.     return( ( input->n_players == my_census.census.n_players ) &&
  776.             ( input->chksum == my_census.census.chksum ) &&
  777.             ( input->chkxor == my_census.census.chkxor ) ) ;
  778. }
  779.  
  780.  
  781.  
  782. /*------------------------------------------------------------------------------
  783.  * Process a census packet.
  784.  *----------------------------------------------------------------------------*/
  785. void process_bz_census(
  786.     struct BzCensus    *input
  787.     )
  788. {
  789.     int                        n ;
  790.     int                        i ;
  791.     struct bz_census        *pcen ;
  792.     struct bz_host            *host ;
  793.  
  794.     if( ( n = find_player( input->id ) ) > 0 ) {
  795.         /*
  796.          * Save the census packet.
  797.          */
  798.         if( ( pcen = find_host_census( input->id ) ) == NULL ) {
  799. #if defined( NETDEBUGGER )
  800.             post_new_message( 0, 0, "could not find CENSUS for %c",
  801.                               'a' + input->id ) ;
  802. #endif /* defined( NETDEBUGGER ) */
  803.             return ;
  804.             }
  805.         else {
  806.             copybytes( input, &(pcen->census), sizeof( struct BzCensus ) ) ;
  807.             }
  808.         /*
  809.          * Check if census matches up with SELF's census.
  810.          */
  811.         if( compare_census( input ) ) {
  812.             /*
  813.              * It matches, so set new deadline for player.
  814.              */
  815.             set_time( &(deadline[n]), ¤t_time, BZ_OLD_DEADLINE_TIME, 0 ) ;
  816.             if( ( host = find_host( input->id ) ) != NULL ) {
  817.                 if( host->agrees == 0 ) {
  818.                     dprintf( "%s: validation now matching from %s.\n",
  819.                              print_time(), host_name_from_id( host->id ) ) ;
  820.                     host->agrees = 1 ;
  821.                     }
  822.                 }
  823.             }
  824.         else {
  825.             /*
  826.              * No match.  See if player's deadline has been exceeded.
  827.              */
  828.             if( ( host = find_host( input->id ) ) != NULL ) {
  829.                 if( host->agrees == 1 ) {
  830.                     dprintf( "%s: validation no longer matches from %s.\n",
  831.                              print_time(), host_name_from_id( host->id ) ) ;
  832.                     host->agrees = 0 ;
  833.                     }
  834.                 }
  835.             if( elapsed_sec_tenths( &(deadline[n]), ¤t_time ) > 0 ) {
  836.                 /*
  837.                  * Deadline passed, drop player.
  838.                  */
  839.                 invalidate_host( input->id ) ;
  840.                 delete_player( n, "was invalidated" ) ;
  841.                 }
  842.  
  843.             /*
  844.              * Set time between census broadcasts to a smaller number since
  845.              * the census lists are in flux.
  846.              */
  847.             time_between_census_posts = BZ_UNSTEADY_CENSUS_RATE ;
  848.             }
  849.         }
  850. }
  851.  
  852.  
  853.  
  854. /*------------------------------------------------------------------------------
  855.  * Check to see if we need to send a census packet.
  856.  *----------------------------------------------------------------------------*/
  857. void check_to_send_census( void )
  858. {
  859.     long    tenths ;
  860.  
  861.     if( need_to_do_weeding &&
  862.         elapsed_sec_tenths( &weed_time, ¤t_time ) > 0 ){
  863.         do_weeding() ;
  864.         need_to_do_weeding = FALSE ;
  865.         }
  866.  
  867.     if( need_to_send_census ||
  868.         elapsed_sec_tenths( &last_census_sent, ¤t_time ) >
  869.                     time_between_census_posts ) {
  870.         need_to_send_census = FALSE ;
  871.         send_out( &(my_census.census), sizeof( struct BzCensus ) ) ;
  872.         copy_time( &last_census_sent, ¤t_time ) ;
  873.         time_between_census_posts = BZ_STEADY_CENSUS_RATE ;
  874.         }
  875. }
  876.  
  877.  
  878.  
  879. /*------------------------------------------------------------------------------
  880.  * Reset all of the census deadlines except for the newest.
  881.  *----------------------------------------------------------------------------*/
  882. static void reset_deadlines(
  883.     int except
  884.     )
  885. {
  886.     int                        i ;
  887.     long                    secs ;
  888.     long                    tenths ;
  889.  
  890.     if( ( secs = elapsed_sec_tenths( &last_census_sent, ¤t_time ) ) <
  891.             BZ_OLD_DEADLINE_TIME * 10 ) {
  892.  
  893.         tenths = secs % 10 ;
  894.         secs /= 10 ;
  895. #if defined( NETDEBUGGER )
  896.         post_new_message( 0, 0, "%s increasing deadline by %ld.%ld secs",
  897.                           print_time(), secs, tenths ) ;
  898. #endif /* defined( NETDEBUGGER ) */
  899.  
  900.         for( i = ENEMY ; i < number_players ; i++ ) {
  901.             if( i != except ) {
  902.                 set_time( &(deadline[i]), &(deadline[i]), secs, tenths ) ;
  903. #if defined( NETDEBUGGER )
  904.                 dprintf( "deadline for %s is %s",
  905.                         host_name_from_id( player[i].id ),
  906.                         print_time_hundreths( &(deadline[i]) ) ) ;
  907. #endif /* defined( NETDEBUGGER ) */
  908.                 }
  909.             }
  910.         }
  911. }
  912.  
  913.  
  914.  
  915. /*------------------------------------------------------------------------------
  916.  * Print out a list of all non-valid hosts and a guess at why.
  917.  *----------------------------------------------------------------------------*/
  918. void validation_summary( void )
  919. {
  920.     struct bz_host    *host = first_host ;
  921.  
  922.     while( host ) {
  923.         switch( host->valid ) {
  924.  
  925.             case BZ_VALID_UNKNOWN :
  926.                 if( host->drops ) {
  927.                     dprintf( "Lost communcation from host %s.\n",
  928.                              host_name_from_id( host->id ) ) ;
  929.                     }
  930.                 else {
  931.                     dprintf( "Host %s evidently could not receive my packets."
  932.                              "\n", host_name_from_id( host->id ) ) ;
  933.                     }
  934.                 break ;
  935.  
  936.             case BZ_VALID :
  937.                 dprintf( "Host %s was valid.\n",
  938.                          host_name_from_id( host->id ) ) ;
  939.                 break ;
  940.  
  941.             case BZ_INVALID :
  942.                 break ;
  943.  
  944.             case BZ_VALID_QUIT :
  945.                 dprintf( "Host %s has quit (validity unknown).\n",
  946.                          host_name_from_id( host->id ) ) ;
  947.                 break ;
  948.  
  949.             case BZ_DROPPED :
  950.                 dprintf(
  951.                          "Host %s evidently stopped receiving my packets.\n",
  952.                          host_name_from_id( host->id ) ) ;
  953.                 break ;
  954.  
  955.             default :
  956.                 dprintf( "Odd validity for %s.\n",
  957.                          host_name_from_id( host->id ) ) ;
  958.                 break ;
  959.             }
  960.         host = host->next ;
  961.         }
  962.  
  963.     dprintf( "end" ) ;
  964. }
  965.  
  966.  
  967.  
  968. /*------------------------------------------------------------------------------
  969.  * Convert a `hostid' number to a string representing the host's name if
  970.  * known, otherwise the IP address.
  971.  *----------------------------------------------------------------------------*/
  972. char *host_name_from_id(
  973.     long id
  974.     )
  975. {
  976.     struct in_addr    addr ;
  977.     struct hostent    *hp ;
  978.     static char        buffer[256] ;
  979.  
  980. #if !defined( NETDEBUGGER )
  981.     addr.s_addr = id ;
  982.     hp = gethostbyaddr( &addr, sizeof(addr), AF_INET ) ;
  983.     if( hp ) {
  984.         sprintf( buffer, "%s (%s)", hp->h_name, inet_ntoa(addr) ) ;
  985.         }
  986.     else {
  987.         sprintf( buffer, "%s", inet_ntoa(addr) ) ;
  988.         }
  989. #else
  990.     sprintf( buffer, "player %c", 'a' + id ) ;
  991. #endif /* !defined( NETDEBUGGER ) */
  992.  
  993.     return( buffer ) ;
  994. }
  995.  
  996.  
  997.  
  998. /*------------------------------------------------------------------------------
  999.  * Send out an ACK packet.
  1000.  *---------------------------------------------------------------------------*/
  1001. void send_acknowledgement(
  1002.     long id
  1003.     )
  1004. {
  1005.     struct BzAck            ack ;
  1006.  
  1007.     ack.bz_id = BZACK ;
  1008.     ack.id = player[SELF].id ;
  1009.     ack.ack_id = id ;
  1010.     ack.key = player[SELF].key ;
  1011.     send_out( &ack, sizeof( ack ) ) ;
  1012. }
  1013.  
  1014.  
  1015.  
  1016. /*------------------------------------------------------------------------------
  1017.  * Spit out a list of all the hosts.
  1018.  *----------------------------------------------------------------------------*/
  1019. static void list_hosts( void )
  1020. {
  1021.     int                i = 0 ;
  1022.     struct bz_host    *host = first_host ;
  1023.  
  1024.     while( host != NULL ) {
  1025. #if defined( NETDEBUGGER )
  1026.         post_new_message( 0, 0, "%d - %c (%hd,%hd) %hd", i, 'a'+host->id,
  1027.                           host->drops, host->acks, host->valid ) ;
  1028. #else
  1029.         post_new_message( 0, 0, "%d - %s (%hd,%hd) %hd", i,
  1030.                           host_name_from_id( host->id ), host->drops,
  1031.                           host->acks, host->valid ) ;
  1032. #endif /* defined( NETDEBUGGER ) */
  1033.         host = host->next ;
  1034.         }
  1035.  
  1036.     return ;
  1037. }
  1038.  
  1039.  
  1040.  
  1041. /*------------------------------------------------------------------------------
  1042.  * Do initial weeding of host to try and join the largest group.
  1043.  *----------------------------------------------------------------------------*/
  1044. static void do_weeding( void )
  1045. {
  1046.     int                        i ;
  1047.     int                        j ;
  1048.     int                        n ;
  1049.     int                        total ;
  1050.     int                        best_total = 0 ;
  1051.     int                        least_seen ;
  1052.     int                        times_seen[MAXPLAYERS] ;
  1053.     struct bz_census        *next = my_census.next ;
  1054.     struct bz_census        *prev = &my_census ;
  1055.     struct bz_census        *best ;
  1056.  
  1057. #if defined( NETDEBUGGER )
  1058.     post_new_message( 0, 0, "%s doing initial weeding", print_time() ) ;
  1059. #endif /* defined( NETDEBUGGER ) */
  1060.  
  1061.     /*
  1062.      * Go through all players in my census and mark as being seen once (by me).
  1063.      */
  1064.     for( i = 0 ; i < my_census.census.n_players ; i++ ) {
  1065.         times_seen[i] = 1 ;
  1066.         }
  1067.  
  1068.     /*
  1069.      * Go through all other players and mark players according to how many
  1070.      * times they appear on other's censuses.
  1071.      */
  1072.     while( next ) {
  1073.         total = 0 ;
  1074.         for( i = 0 ; i < next->census.n_players ; i++ ) {
  1075.             /*
  1076.              * Check if host is on my census.
  1077.              */
  1078.             n = find_host_in_my_census_list( next->census.list[i] ) ;
  1079.             /*
  1080.              * If host is in my census, increment total and mark player.
  1081.              */
  1082.             if( n != -1 ) {
  1083.                 total++ ;
  1084.                 times_seen[n] += 1 ;
  1085.                 }
  1086.             }
  1087.         /*
  1088.          * Check number of census matches.
  1089.          */
  1090.         if( total > best_total ) {
  1091.             best = next ;
  1092.             best_total = total ;
  1093.             }
  1094.         next = next->next ;
  1095.         }
  1096.  
  1097. #if defined( NETDEBUGGER )
  1098.     for( i = 0 ; i < my_census.census.n_players ; i++ ) {
  1099.         post_new_message( 0, 0, "*        * %c seen %d times",
  1100.             'a' + my_census.census.list[i], times_seen[i] ) ;
  1101.         }
  1102. #endif /* defined( NETDEBUGGER ) */
  1103.  
  1104.     /*
  1105.      * If the best match is greater than zero...
  1106.      */
  1107.     if( best_total > 0 && best != NULL ) {
  1108.  
  1109. #if defined( NETDEBUGGER )
  1110.         post_new_message( 0, 0, "*        * best total = %d/%d (player %c)",
  1111.                             best_total, best->census.n_players,
  1112.                             'a' + best->census.id ) ;
  1113. #endif /* defined( NETDEBUGGER ) */
  1114.  
  1115.         /*
  1116.          * Compare my census with the best match.
  1117.          */
  1118.         j = 0 ;
  1119.         least_seen = best_total + 1 ;
  1120.         for( i = 0 ; i < my_census.census.n_players ; i++ ) {
  1121.             /*
  1122.              * Find location in best census where my i-th census entry
  1123.              * should be.
  1124.              */
  1125.             while( j < best->census.n_players &&
  1126.                    my_census.census.list[i] > best->census.list[j] ) {
  1127.                 j++ ;
  1128.                 }
  1129.             /*
  1130.              * If i-th entry is in best census, check for least seen value.
  1131.              */
  1132.             if( j < best->census.n_players &&
  1133.                 my_census.census.list[i] == best->census.list[j] ) {
  1134.                 if( times_seen[i] <= least_seen ) {
  1135.                     least_seen = times_seen[i] ;
  1136.                     }
  1137.                 j++ ;
  1138.                 }
  1139.             /*
  1140.              * The i-th entry isn't in the best census, so shorten it's
  1141.              * deadline.
  1142.              */
  1143.             else {
  1144.                 if( ( n = find_player( my_census.census.list[i] ) ) > 0 ) {
  1145.                     set_time( &(deadline[n]), &(deadline[n]),
  1146.                               BZ_DROPPING_DELTA, 0 ) ;
  1147. #if defined( NETDEBUGGER )
  1148.                     post_new_message( 0, 0, "*        * should_drop %c (%s)",
  1149.                         'a' + my_census.census.list[i],
  1150.                         print_time_hundreths( &(deadline[n]) ) ) ;
  1151. #endif /* defined( NETDEBUGGER ) */
  1152.                     }
  1153.                 }
  1154.             }
  1155.  
  1156. #if defined( NETDEBUGGER )
  1157.         post_new_message( 0, 0, "*        * least_seen = %d", least_seen ) ;
  1158. #endif /* defined( NETDEBUGGER ) */
  1159.  
  1160.         /*
  1161.          * If some entry is seen less times than the best total, shorten
  1162.          * its deadline time.
  1163.          */
  1164.         if( least_seen < best_total ) {
  1165.             for( i = 0 ; i < my_census.census.n_players ; i++ ) {
  1166.                 if( times_seen[i] == least_seen ) {
  1167.                     /*
  1168.                      * Decrease deadline.
  1169.                      */
  1170.                     if( ( n = find_player( my_census.census.list[i] ) ) > 0 ) {
  1171.                         set_time( &(deadline[n]), &(deadline[n]),
  1172.                                   BZ_DROPPING_DELTA, 0 ) ;
  1173. #if defined( NETDEBUGGER )
  1174.                         post_new_message( 0, 0,
  1175.                             "*        * should_drop %c (%s)",
  1176.                             'a' + my_census.census.list[i],
  1177.                             print_time_hundreths( &(deadline[n]) ) ) ;
  1178. #endif /* defined( NETDEBUGGER ) */
  1179.                         }
  1180.                     }
  1181.                 }
  1182.             }
  1183.         }
  1184.  
  1185. #if defined( NETDEBUGGER )
  1186.     post_new_message( 0, 0, "********** ending weeding" ) ;
  1187. #endif /* defined( NETDEBUGGER ) */
  1188. }
  1189.  
  1190.  
  1191.  
  1192. /*------------------------------------------------------------------------------
  1193.  * Debug printf.
  1194.  *----------------------------------------------------------------------------*/
  1195. void dprintf(
  1196.     char *fmt,
  1197.     ...
  1198.     )
  1199. {
  1200.     va_list        args ;
  1201.     static int    status = 0 ;
  1202.     static FILE    *debug_out ;
  1203.  
  1204.     if( status == -1 ) {
  1205.         return ;
  1206.         }
  1207.  
  1208.     if( strcmp( fmt, "end" ) == 0 ) {
  1209. #if !defined( NETDEBUGGER )
  1210.         if( status == 1 ) {
  1211.             fclose( debug_out ) ;
  1212.             printf( "Summary of validations written to /usr/tmp/bz.log\n" ) ;
  1213.             }
  1214. #endif /* !defined( NETDEBUGGER ) */
  1215.         return ;
  1216.         }
  1217.     else if( strcmp( fmt, "disable" ) == 0 ) {
  1218.         status = -1 ;
  1219.         return ;
  1220.         }
  1221.  
  1222.     if( status == 0 ) {
  1223. #if defined( NETDEBUGGER )
  1224.         status = 1 ;
  1225. #else
  1226.         if( ( debug_out = fopen( "/usr/tmp/bz.log", "w" ) ) == NULL ) {
  1227.             status = -1 ;
  1228.             return ;
  1229.             }
  1230.         else {
  1231.             status = 1 ;
  1232.             }
  1233. #endif /* defined( NETDEBUGGER ) */
  1234.         }
  1235.  
  1236.     va_start( args, fmt ) ;
  1237. #if defined( NETDEBUGGER )
  1238.     print_to_net_debugger( fmt, args ) ;
  1239. #else
  1240.     vfprintf( debug_out, fmt, args ) ;
  1241. #endif /* defined( NETDEBUGGER ) */
  1242.     va_end( args ) ;
  1243. }
  1244.  
  1245.  
  1246.  
  1247. /*------------------------------------------------------------------------------
  1248.  * Print out the time.
  1249.  *----------------------------------------------------------------------------*/
  1250. char *print_time( void )
  1251. {
  1252.     static char    timestr[64] ;
  1253.     time_t        clock_val ;
  1254.  
  1255.     clock_val = time( NULL ) ;
  1256.  
  1257.     cftime( timestr, "%r", &clock_val ) ;
  1258.  
  1259.     return( timestr ) ;
  1260. }
  1261.  
  1262.  
  1263.  
  1264. /*------------------------------------------------------------------------------
  1265.  * Print out the date.
  1266.  *----------------------------------------------------------------------------*/
  1267. char *print_date( void )
  1268. {
  1269.     static char    datestr[64] ;
  1270.     time_t        clock_val ;
  1271.  
  1272.     clock_val = time( NULL ) ;
  1273.  
  1274.     cftime( datestr, "%D", &clock_val ) ;
  1275.  
  1276.     return( datestr ) ;
  1277. }
  1278.  
  1279.  
  1280.  
  1281. /*------------------------------------------------------------------------------
  1282.  * Print out the time with hundreths of seconds.
  1283.  *----------------------------------------------------------------------------*/
  1284. char *print_time_hundreths(
  1285.     struct timeval *t
  1286.     )
  1287. {
  1288.     static char    timestr[64] ;
  1289.     int            i ;
  1290.     time_t        secs ;
  1291.     long        hsecs ;
  1292.  
  1293.     secs = t->tv_sec + t->tv_usec / 1000000 ;
  1294.     hsecs = ( t->tv_usec % 1000000 ) / 10000 ;
  1295.     cftime( timestr, "%I:%M:%S.00 %p", &secs ) ;
  1296.     i = strlen( timestr ) ;
  1297.  
  1298.     sprintf( timestr + 9, "%02d", hsecs ) ;
  1299.     timestr[11] = ' ' ;
  1300.  
  1301.     return( timestr ) ;
  1302. }
  1303.  
  1304.  
  1305.  
  1306.