aboutsummaryrefslogtreecommitdiffstats
path: root/docs/pathod/intro.rst
blob: bf0c531fd55a682028d9703c2ac71f6c280b0a3c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
.. _intro:

Pathology 101
=============


pathod
------

Pathod is a pathological HTTP daemon designed to let you craft almost any
conceivable HTTP response, including ones that creatively violate the
standards. HTTP responses are specified using a :ref:`small, terse language
<language>` which pathod shares with its evil twin :ref:`pathoc`. To start
playing with pathod, fire up the daemon:

>>> pathod

By default, the service listens on port 9999 of localhost, and the default
crafting anchor point is the path **/p/**. Anything after this URL prefix is
treated as a response specifier. So, hitting the following URL will generate an
HTTP 200 response with 100 bytes of random data:

    http://localhost:9999/p/200:b@100

See the :ref:`language documentation <language>` to get (much) fancier. The
pathod daemon also takes a range of configuration options. To view those, use
the command-line help:

>>> pathod --help

Mimicing a proxy
^^^^^^^^^^^^^^^^

Pathod automatically responds to both straight HTTP and proxy requests. For
proxy requests, the upstream host is ignored, and the path portion of the URL
is used to match anchors. This lets you test software that supports a proxy
configuration by spoofing responses from upstream servers.

By default, we treat all proxy CONNECT requests as HTTPS traffic, serving the
response using either pathod's built-in certificates, or the cert/key pair
specified by the user. You can over-ride this behaviour if you're testing a
client that makes a non-SSL CONNECT request using the **-C** command-line
option.

Anchors
^^^^^^^

Anchors provide an alternative to specifying the response in the URL. Instead,
you attach a response to a pre-configured anchor point, specified with a regex.
When a URL matching the regex is requested, the specified response is served.

>>> pathod -a "/foo=200"

Here, "/foo" is the regex specifying the anchor path, and the part after the "="
is a response specifier.


File Access
^^^^^^^^^^^

There are two operators in the :ref:`language <language>` that load contents
from file - the **+** operator to load an entire request specification from
file, and the **>** value specifier. In pathod, both of these operators are
restricted to a directory specified at startup, or disabled if no directory is
specified:

>>> pathod -d ~/staticdir"


Internal Error Responses
^^^^^^^^^^^^^^^^^^^^^^^^

Pathod uses the non-standard 800 response code to indicate internal errors, to
distinguish them from crafted responses. For example, a request to:

    http://localhost:9999/p/foo

... will return an 800 response because "foo" is not a valid page specifier.





.. _pathoc:


pathoc
------

Pathoc is a perverse HTTP daemon designed to let you craft almost any
conceivable HTTP request, including ones that creatively violate the standards.
HTTP requests are specified using a :ref:`small, terse language <language>`,
which pathod shares with its server-side twin pathod. To view pathoc's complete
range of options, use the command-line help:

>>> pathoc --help


Getting Started
^^^^^^^^^^^^^^^

The basic pattern for pathoc commands is as follows:

    pathoc hostname request [request ...]

That is, we specify the hostname to connect to, followed by one or more
requests. Lets start with a simple example::

    > pathoc google.com get:/
    07-06-16 12:13:43: >> 'GET':/
    << 302 Found: 261 bytes

Here, we make a GET request to the path / on port 80 of google.com. Pathoc's
output tells us that the server responded with a 302 redirection. We can tell
pathoc to connect using SSL, in which case the default port is changed to 443
(you can over-ride the default port with the **-p** command-line option)::

    > pathoc -s www.google.com get:/
    07-06-16 12:14:56: >> 'GET':/
    << 302 Found: 262 bytes


Multiple Requests
^^^^^^^^^^^^^^^^^

There are two ways to tell pathoc to issue multiple requests. The first is to specify
them on the command-line, like so::

    > pathoc google.com get:/ get:/
    07-06-16 12:21:04: >> 'GET':/
    << 302 Found: 261 bytes
    07-06-16 12:21:04: >> 'GET':/
    << 302 Found: 261 bytes

In this case, pathoc issues the specified requests over the same TCP connection -
so in the above example only one connection is made to google.com

The other way to issue multiple requests is to use the **-n** flag::

    > pathoc -n 2 google.com get:/
    07-06-16 12:21:04: >> 'GET':/
    << 302 Found: 261 bytes
    07-06-16 12:21:04: >> 'GET':/
    << 302 Found: 261 bytes

The output is identical, but two separate TCP connections are made to the
upstream server. These two specification styles can be combined::

    pathoc -n 2 google.com get:/ get:/


Here, two distinct TCP connections are made, with two requests issued over
each.



Basic Fuzzing
^^^^^^^^^^^^^

The combination of pathoc's powerful request specification language and a few
of its command-line options makes for quite a powerful basic fuzzer. Here's an
example::

    pathoc -e -I 200 -t 2 -n 1000 localhost get:/:b@10:ir,@1

The request specified here is a valid GET with a body consisting of 10 random bytes,
but with 1 random byte inserted in a random place. This could be in the headers,
in the initial request line, or in the body itself. There are a few things
to note here:

- Corrupting the request in this way will often make the server enter a state where
  it's awaiting more input from the client. This is where the
  **-t** option comes in, which sets a timeout that causes pathoc to
  disconnect after two seconds.
- The **-n** option tells pathoc to repeat the request 1000 times.
- The **-I** option tells pathoc to ignore HTTP 200 response codes.
  You can use this to fine-tune what pathoc considers to be an exceptional
  condition, and therefore log-worthy.
- The **-e** option tells pathoc to print an explanation of each logged
  request, in the form of an expanded pathoc specification with all random
  portions and automatic header additions resolved. This lets you precisely
  replay a request that triggered an error.


Interacting with Proxies
^^^^^^^^^^^^^^^^^^^^^^^^

Pathoc has a reasonably sophisticated suite of features for interacting with
proxies. The proxy request syntax very closely mirrors that of straight HTTP,
which means that it is possible to make proxy-style requests using pathoc
without any additional syntax, by simply specifying a full URL instead of a
simple path:

>>> pathoc -p 8080 localhost "get:'http://google.com'"

Another common use case is to use an HTTP CONNECT request to probe remote
servers via a proxy. This is done with the **-c** command-line option, which
allows you to specify a remote host and port pair:

>>> pathoc -c google.com:80 -p 8080 localhost get:/

Note that pathoc does **not** negotiate SSL without being explictly instructed
to do so. If you're making a CONNECT request to an SSL-protected resource, you
must also pass the **-s** flag:

>>> pathoc -sc google.com:443 -p 8080 localhost get:/



Embedded response specification
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

One interesting feature of the Request specification language is that you can
embed a response specification in it, which is then added to the request path.
Here's an example:

>>> pathoc localhost:9999 "get:/p/:s'401:ir,@1'"

This crafts a request that connects to the pathod server, and which then crafts
a response that generates a 401, with one random byte embedded at a random
point. The response specification is parsed and expanded by pathoc, so you see
syntax errors immediately. This really becomes handy when combined with the
**-e** flag to show the expanded request::

    07-06-16 12:32:01: >> 'GET':/p/:s'401:i35,\x27\\x1b\x27:h\x27Content-Length\x27=\x270\x27:h\x27Content-Length\x27=\x270\x27':h'Host'='localhost'
    << 401 Unauthorized: 0 bytes

Note that the embedded response has been resolved *before* being sent to
the server, so that "ir,@1" (embed a random byte at a random location) has
become "i15,\'o\'" (embed the character "o" at offset 15). You now have a
pathoc request specification that is precisely reproducible, even with random
components. This feature comes in terribly handy when testing a proxy, since
you can now drive the server response completely from the client, and have a
complete log of reproducible requests to analyze afterwards.


Request Examples
----------------

.. list-table::
    :widths: 50 50
    :header-rows: 0

    * - get:/
      - Get path /

    * - get:/:b@100
      - 100 random bytes as the body

    * - get:/:h"Etag"="&;drop table browsers;"
      - Add a header

    * - get:/:u"&;drop table browsers;"
      - Add a User-Agent header

    * - get:/:b@100:dr
      - Drop the connection randomly

    * - get:/:b@100,ascii:ir,@1
      - 100 ASCII bytes as the body, and randomly inject a random byte

    * - ws:/
      - Initiate a websocket handshake.


Response Examples
-----------------

.. list-table::
    :widths: 50 50
    :header-rows: 0


    * - 200
      - A basic HTTP 200 response.

    * - 200:r
      - A basic HTTP 200 response with no Content-Length header. This will hang.

    * - 200:da
      - Server-side disconnect after all content has been sent.

    * - 200:b\@100
      - 100 random bytes as the body. A Content-Length header is added, so the disconnect
        is no longer needed.

    * - 200:b\@100:h"Etag"="';drop table servers;"
      - Add a Server header

    * - 200:b\@100:dr
      - Drop the connection randomly

    * - 200:b\@100,ascii:ir,@1
      - 100 ASCII bytes as the body, and randomly inject a random byte

    * - 200:b\@1k:c"text/json"
      - 1k of random bytes, with a text/json content type

    * - 200:b\@1k:p50,120
      - 1k of random bytes, pause for 120 seconds after 50 bytes

    * - 200:b\@1k:pr,f
      - 1k of random bytes, but hang forever at a random location

    * - 200:b\@100:h\@1k,ascii_letters='foo'
      - 100 ASCII bytes as the body, randomly generated 100k header name, with the value
        'foo'.
a> 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071
/**CFile****************************************************************

  FileName    [vecPtr.h]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Resizable arrays.]

  Synopsis    [Resizable arrays of generic pointers.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: vecPtr.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/
 
#ifndef ABC__misc__vec__vecPtr_h
#define ABC__misc__vec__vecPtr_h


////////////////////////////////////////////////////////////////////////
///                          INCLUDES                                ///
////////////////////////////////////////////////////////////////////////

#include <stdio.h>

ABC_NAMESPACE_HEADER_START


////////////////////////////////////////////////////////////////////////
///                         PARAMETERS                               ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                         BASIC TYPES                              ///
////////////////////////////////////////////////////////////////////////

typedef struct Vec_Ptr_t_       Vec_Ptr_t;
struct Vec_Ptr_t_ 
{
    int              nCap;
    int              nSize;
    void **          pArray;
};

////////////////////////////////////////////////////////////////////////
///                      MACRO DEFINITIONS                           ///
////////////////////////////////////////////////////////////////////////

// iterators through entries
#define Vec_PtrForEachEntry( Type, vVec, pEntry, i )                                               \
    for ( i = 0; (i < Vec_PtrSize(vVec)) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i++ )
#define Vec_PtrForEachEntryStart( Type, vVec, pEntry, i, Start )                                   \
    for ( i = Start; (i < Vec_PtrSize(vVec)) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i++ )
#define Vec_PtrForEachEntryStop( Type, vVec, pEntry, i, Stop )                                     \
    for ( i = 0; (i < Stop) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i++ )
#define Vec_PtrForEachEntryStartStop( Type, vVec, pEntry, i, Start, Stop )                         \
    for ( i = Start; (i < Stop) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i++ )
#define Vec_PtrForEachEntryReverse( Type, vVec, pEntry, i )                                        \
    for ( i = Vec_PtrSize(vVec) - 1; (i >= 0) && (((pEntry) = (Type)Vec_PtrEntry(vVec, i)), 1); i-- )

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Allocates a vector with the given capacity.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrAlloc( int nCap )
{
    Vec_Ptr_t * p;
    p = ABC_ALLOC( Vec_Ptr_t, 1 );
    if ( nCap > 0 && nCap < 8 )
        nCap = 8;
    p->nSize  = 0;
    p->nCap   = nCap;
    p->pArray = p->nCap? ABC_ALLOC( void *, p->nCap ) : NULL;
    return p;
}

/**Function*************************************************************

  Synopsis    [Allocates a vector with the given size and cleans it.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrStart( int nSize )
{
    Vec_Ptr_t * p;
    p = Vec_PtrAlloc( nSize );
    p->nSize = nSize;
    memset( p->pArray, 0, sizeof(void *) * nSize );
    return p;
}

/**Function*************************************************************

  Synopsis    [Creates the vector from an integer array of the given size.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrAllocArray( void ** pArray, int nSize )
{
    Vec_Ptr_t * p;
    p = ABC_ALLOC( Vec_Ptr_t, 1 );
    p->nSize  = nSize;
    p->nCap   = nSize;
    p->pArray = pArray;
    return p;
}

/**Function*************************************************************

  Synopsis    [Creates the vector from an integer array of the given size.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrAllocArrayCopy( void ** pArray, int nSize )
{
    Vec_Ptr_t * p;
    p = ABC_ALLOC( Vec_Ptr_t, 1 );
    p->nSize  = nSize;
    p->nCap   = nSize;
    p->pArray = ABC_ALLOC( void *, nSize );
    memcpy( p->pArray, pArray, sizeof(void *) * nSize );
    return p;
}

/**Function*************************************************************

  Synopsis    [Duplicates the integer array.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrDup( Vec_Ptr_t * pVec )
{
    Vec_Ptr_t * p;
    p = ABC_ALLOC( Vec_Ptr_t, 1 );
    p->nSize  = pVec->nSize;
    p->nCap   = pVec->nCap;
    p->pArray = p->nCap? ABC_ALLOC( void *, p->nCap ) : NULL;
    memcpy( p->pArray, pVec->pArray, sizeof(void *) * pVec->nSize );
    return p;
}
static inline Vec_Ptr_t * Vec_PtrDupStr( Vec_Ptr_t * pVec )
{
    int i;
    Vec_Ptr_t * p = Vec_PtrDup( pVec );
    for ( i = 0; i < p->nSize; i++ )
        p->pArray[i] = Abc_UtilStrsav( (char *)p->pArray[i] );
    return p;
}

/**Function*************************************************************

  Synopsis    [Transfers the array into another vector.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrDupArray( Vec_Ptr_t * pVec )
{
    Vec_Ptr_t * p;
    p = ABC_ALLOC( Vec_Ptr_t, 1 );
    p->nSize  = pVec->nSize;
    p->nCap   = pVec->nCap;
    p->pArray = pVec->pArray;
    pVec->nSize  = 0;
    pVec->nCap   = 0;
    pVec->pArray = NULL;
    return p;
}

/**Function*************************************************************

  Synopsis    [Frees the vector.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrFree( Vec_Ptr_t * p )
{
    ABC_FREE( p->pArray );
    ABC_FREE( p );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrFreeP( Vec_Ptr_t ** p )
{
    if ( *p == NULL )
        return;
    ABC_FREE( (*p)->pArray );
    ABC_FREE( (*p) );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void ** Vec_PtrReleaseArray( Vec_Ptr_t * p )
{
    void ** pArray = p->pArray;
    p->nCap = 0;
    p->nSize = 0;
    p->pArray = NULL;
    return pArray;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void ** Vec_PtrArray( Vec_Ptr_t * p )
{
    return p->pArray;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrSize( Vec_Ptr_t * p )
{
    return p->nSize;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrCap( Vec_Ptr_t * p )
{
    return p->nCap;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline double Vec_PtrMemory( Vec_Ptr_t * p )
{
    return !p ? 0.0 : 1.0 * sizeof(void *) * p->nCap + sizeof(Vec_Ptr_t);
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrCountZero( Vec_Ptr_t * p ) 
{
    int i, Counter = 0;
    for ( i = 0; i < p->nSize; i++ )
        Counter += (p->pArray[i] == NULL);
    return Counter;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void * Vec_PtrEntry( Vec_Ptr_t * p, int i )
{
    assert( i >= 0 && i < p->nSize );
    return p->pArray[i];
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void ** Vec_PtrEntryP( Vec_Ptr_t * p, int i )
{
    assert( i >= 0 && i < p->nSize );
    return p->pArray + i;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrWriteEntry( Vec_Ptr_t * p, int i, void * Entry )
{
    assert( i >= 0 && i < p->nSize );
    p->pArray[i] = Entry;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void * Vec_PtrEntryLast( Vec_Ptr_t * p )
{
    assert( p->nSize > 0 );
    return p->pArray[p->nSize-1];
}

/**Function*************************************************************

  Synopsis    [Resizes the vector to the given capacity.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrGrow( Vec_Ptr_t * p, int nCapMin )
{
    if ( p->nCap >= nCapMin )
        return;
    p->pArray = ABC_REALLOC( void *, p->pArray, nCapMin ); 
    p->nCap   = nCapMin;
}

/**Function*************************************************************

  Synopsis    [Fills the vector with given number of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrFill( Vec_Ptr_t * p, int nSize, void * Entry )
{
    int i;
    Vec_PtrGrow( p, nSize );
    for ( i = 0; i < nSize; i++ )
        p->pArray[i] = Entry;
    p->nSize = nSize;
}

/**Function*************************************************************

  Synopsis    [Fills the vector with given number of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrFillExtra( Vec_Ptr_t * p, int nSize, void * Fill )
{
    int i;
    if ( nSize <= p->nSize )
        return;
    if ( nSize > 2 * p->nCap )
        Vec_PtrGrow( p, nSize );
    else if ( nSize > p->nCap )
        Vec_PtrGrow( p, 2 * p->nCap );
    for ( i = p->nSize; i < nSize; i++ )
        p->pArray[i] = Fill;
    p->nSize = nSize;
}

/**Function*************************************************************

  Synopsis    [Returns the entry even if the place not exist.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void * Vec_PtrGetEntry( Vec_Ptr_t * p, int i )
{
    Vec_PtrFillExtra( p, i + 1, NULL );
    return Vec_PtrEntry( p, i );
}

/**Function*************************************************************

  Synopsis    [Inserts the entry even if the place does not exist.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrSetEntry( Vec_Ptr_t * p, int i, void * Entry )
{
    Vec_PtrFillExtra( p, i + 1, NULL );
    Vec_PtrWriteEntry( p, i, Entry );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrShrink( Vec_Ptr_t * p, int nSizeNew )
{
    assert( p->nSize >= nSizeNew );
    p->nSize = nSizeNew;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrClear( Vec_Ptr_t * p )
{
    p->nSize = 0;
}

/**Function*************************************************************

  Synopsis    [Deallocates array of memory pointers.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrFreeFree( Vec_Ptr_t * p )
{
    void * pTemp;
    int i;
    if ( p == NULL ) return;
    Vec_PtrForEachEntry( void *, p, pTemp, i )
        if ( pTemp != (void *)(ABC_PTRINT_T)1 && pTemp != (void *)(ABC_PTRINT_T)2 )
            ABC_FREE( pTemp );
    Vec_PtrFree( p );
}

/**Function*************************************************************

  Synopsis    [Copies the interger array.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrCopy( Vec_Ptr_t * pDest, Vec_Ptr_t * pSour )
{
    pDest->nSize = 0;
    Vec_PtrGrow( pDest, pSour->nSize );
    memcpy( pDest->pArray, pSour->pArray, sizeof(void *) * pSour->nSize );
    pDest->nSize = pSour->nSize;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrPush( Vec_Ptr_t * p, void * Entry )
{
    if ( p->nSize == p->nCap )
    {
        if ( p->nCap < 16 )
            Vec_PtrGrow( p, 16 );
        else
            Vec_PtrGrow( p, 2 * p->nCap );
    }
    p->pArray[p->nSize++] = Entry;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrPushFirst( Vec_Ptr_t * p, void * Entry )
{
    int i;
    if ( p->nSize == p->nCap )
    {
        if ( p->nCap < 16 )
            Vec_PtrGrow( p, 16 );
        else
            Vec_PtrGrow( p, 2 * p->nCap );
    }
    p->nSize++;
    for ( i = p->nSize - 1; i >= 1; i-- )
        p->pArray[i] = p->pArray[i-1];
    p->pArray[0] = Entry;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrPushUnique( Vec_Ptr_t * p, void * Entry )
{
    int i;
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == Entry )
            return 1;
    Vec_PtrPush( p, Entry );
    return 0;
}

/**Function*************************************************************

  Synopsis    [Returns the last entry and removes it from the list.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void * Vec_PtrPop( Vec_Ptr_t * p )
{
    assert( p->nSize > 0 );
    return p->pArray[--p->nSize];
}

/**Function*************************************************************

  Synopsis    [Find entry.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrFind( Vec_Ptr_t * p, void * Entry )
{
    int i;
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == Entry )
            return i;
    return -1;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrRemove( Vec_Ptr_t * p, void * Entry )
{
    int i;
    // delete assuming that it is closer to the end
    for ( i = p->nSize - 1; i >= 0; i-- )
        if ( p->pArray[i] == Entry )
            break;
    assert( i >= 0 );
/*
    // delete assuming that it is closer to the beginning
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == Entry )
            break;
    assert( i < p->nSize );
*/
    for ( i++; i < p->nSize; i++ )
        p->pArray[i-1] = p->pArray[i];
    p->nSize--;
}

/**Function*************************************************************

  Synopsis    [Interts entry at the index iHere. Shifts other entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrInsert( Vec_Ptr_t * p, int iHere, void * Entry )
{
    int i;
    assert( iHere >= 0 && iHere < p->nSize );
    Vec_PtrPush( p, 0 );
    for ( i = p->nSize - 1; i > iHere; i-- )
        p->pArray[i] = p->pArray[i-1];
    p->pArray[i] = Entry;
}

/**Function*************************************************************

  Synopsis    [Moves the first nItems to the end.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrReorder( Vec_Ptr_t * p, int nItems )
{
    assert( nItems < p->nSize );
    Vec_PtrGrow( p, nItems + p->nSize );
    memmove( (char **)p->pArray + p->nSize, p->pArray, nItems * sizeof(void*) );
    memmove( p->pArray, (char **)p->pArray + nItems, p->nSize * sizeof(void*) );
}

/**Function*************************************************************

  Synopsis    [Reverses the order of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrReverseOrder( Vec_Ptr_t * p )
{
    void * Temp;
    int i;
    for ( i = 0; i < p->nSize/2; i++ )
    {
        Temp = p->pArray[i];
        p->pArray[i] = p->pArray[p->nSize-1-i];
        p->pArray[p->nSize-1-i] = Temp;
    }
}

/**Function*************************************************************

  Synopsis    [Checks if two vectors are equal.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrEqual( Vec_Ptr_t * p1, Vec_Ptr_t * p2 ) 
{
    int i;
    if ( p1->nSize != p2->nSize )
        return 0;
    for ( i = 0; i < p1->nSize; i++ )
        if ( p1->pArray[i] != p2->pArray[i] )
            return 0;
    return 1;
}

/**Function*************************************************************

  Synopsis    [Comparison procedure for two integers.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static int Vec_PtrSortComparePtr( void ** pp1, void ** pp2 )
{
    if ( *pp1 < *pp2 )
        return -1;
    if ( *pp1 > *pp2 ) 
        return 1;
    return 0; 
}

/**Function*************************************************************

  Synopsis    [Sorting the entries by their integer value.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static void Vec_PtrSort( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) ___unused;
static void Vec_PtrSort( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() )
{
    if ( p->nSize < 2 )
        return;
    if ( Vec_PtrSortCompare == NULL )
        qsort( (void *)p->pArray, p->nSize, sizeof(void *), 
                (int (*)(const void *, const void *)) Vec_PtrSortComparePtr );
    else
        qsort( (void *)p->pArray, p->nSize, sizeof(void *), 
                (int (*)(const void *, const void *)) Vec_PtrSortCompare );
}

/**Function*************************************************************

  Synopsis    [Sorting the entries by their integer value.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static void Vec_PtrUniqify( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) ___unused;
static void Vec_PtrUniqify( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() )
{
    int i, k;
    if ( p->nSize < 2 )
        return;
    Vec_PtrSort( p, Vec_PtrSortCompare );
    for ( i = k = 1; i < p->nSize; i++ )
        if ( p->pArray[i] != p->pArray[i-1] )
            p->pArray[k++] = p->pArray[i];
    p->nSize = k;
}



/**Function*************************************************************

  Synopsis    [Allocates the array of simulation info.]

  Description [Allocates the array containing given number of entries, 
  each of which contains given number of unsigned words of simulation data.
  The resulting array can be freed using regular procedure Vec_PtrFree().
  It is the responsibility of the user to ensure this array is never grown.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrAllocSimInfo( int nEntries, int nWords )
{
    void ** pMemory;
    unsigned * pInfo;
    int i;
    pMemory = (void **)ABC_ALLOC( char, (sizeof(void *) + sizeof(unsigned) * nWords) * nEntries );
    pInfo = (unsigned *)(pMemory + nEntries);
    for ( i = 0; i < nEntries; i++ )
        pMemory[i] = pInfo + i * nWords;
    return Vec_PtrAllocArray( pMemory, nEntries );
}

/**Function*************************************************************

  Synopsis    [Cleans simulation info of each entry beginning with iWord.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrReadWordsSimInfo( Vec_Ptr_t * p )
{
    return (unsigned *)Vec_PtrEntry(p,1) - (unsigned *)Vec_PtrEntry(p,0);
}

/**Function*************************************************************

  Synopsis    [Cleans simulation info of each entry beginning with iWord.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrCleanSimInfo( Vec_Ptr_t * vInfo, int iWord, int nWords )
{
    int i;
    for ( i = 0; i < vInfo->nSize; i++ )
        memset( (char*)Vec_PtrEntry(vInfo,i) + 4*iWord, 0, 4*(nWords-iWord) );
}

/**Function*************************************************************

  Synopsis    [Cleans simulation info of each entry beginning with iWord.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrFillSimInfo( Vec_Ptr_t * vInfo, int iWord, int nWords )
{
    int i;
    for ( i = 0; i < vInfo->nSize; i++ )
        memset( (char*)Vec_PtrEntry(vInfo,i) + 4*iWord, 0xFF, 4*(nWords-iWord) );
}

/**Function*************************************************************

  Synopsis    [Resizes the array of simulation info.]

  Description [Doubles the number of objects for which siminfo is allocated.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrDoubleSimInfo( Vec_Ptr_t * vInfo )
{
    Vec_Ptr_t * vInfoNew;
    int nWords;
    assert( Vec_PtrSize(vInfo) > 1 );
    // get the new array
    nWords = (unsigned *)Vec_PtrEntry(vInfo,1) - (unsigned *)Vec_PtrEntry(vInfo,0);
    vInfoNew = Vec_PtrAllocSimInfo( 2*Vec_PtrSize(vInfo), nWords );
    // copy the simulation info
    memcpy( Vec_PtrEntry(vInfoNew,0), Vec_PtrEntry(vInfo,0), Vec_PtrSize(vInfo) * nWords * 4 );
    // replace the array
    ABC_FREE( vInfo->pArray );
    vInfo->pArray = vInfoNew->pArray;
    vInfo->nSize *= 2;
    vInfo->nCap *= 2;
    // free the old array
    vInfoNew->pArray = NULL;
    ABC_FREE( vInfoNew );
}

/**Function*************************************************************

  Synopsis    [Resizes the array of simulation info.]

  Description [Doubles the number of simulation patterns stored for each object.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrReallocSimInfo( Vec_Ptr_t * vInfo )
{
    Vec_Ptr_t * vInfoNew;
    int nWords, i;
    assert( Vec_PtrSize(vInfo) > 1 );
    // get the new array
    nWords = (unsigned *)Vec_PtrEntry(vInfo,1) - (unsigned *)Vec_PtrEntry(vInfo,0);
    vInfoNew = Vec_PtrAllocSimInfo( Vec_PtrSize(vInfo), 2*nWords );
    // copy the simulation info
    for ( i = 0; i < vInfo->nSize; i++ )
        memcpy( Vec_PtrEntry(vInfoNew,i), Vec_PtrEntry(vInfo,i), nWords * 4 );
    // replace the array
    ABC_FREE( vInfo->pArray );
    vInfo->pArray = vInfoNew->pArray;
    // free the old array
    vInfoNew->pArray = NULL;
    ABC_FREE( vInfoNew );
}

/**Function*************************************************************

  Synopsis    [Allocates the array of truth tables for the given number of vars.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrAllocTruthTables( int nVars )
{
    Vec_Ptr_t * p;
    unsigned Masks[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 };
    unsigned * pTruth;
    int i, k, nWords;
    nWords = (nVars <= 5 ? 1 : (1 << (nVars - 5)));
    p = Vec_PtrAllocSimInfo( nVars, nWords );
    for ( i = 0; i < nVars; i++ )
    {
        pTruth = (unsigned *)p->pArray[i];
        if ( i < 5 )
        {
            for ( k = 0; k < nWords; k++ )
                pTruth[k] = Masks[i];
        }
        else
        {
            for ( k = 0; k < nWords; k++ )
                if ( k & (1 << (i-5)) )
                    pTruth[k] = ~(unsigned)0;
                else
                    pTruth[k] = 0;
        }
    }
    return p;
}



ABC_NAMESPACE_HEADER_END

#endif


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////