int initSemaphores( INOUT KERNEL_DATA *krnlDataPtr )
	{
	int i, status;

	assert( isWritePtr( krnlDataPtr, sizeof( KERNEL_DATA ) ) );

	static_assert( MUTEX_LAST == 4, "Mutex value" );

	/* Set up the reference to the kernel data block */
	krnlData = krnlDataPtr;

	/* Clear the semaphore table */
	for( i = 0; i < SEMAPHORE_LAST; i++ )
		krnlData->semaphoreInfo[ i ] = SEMAPHORE_INFO_TEMPLATE;

	/* Initialize any data structures required to make the semaphore table
	   thread-safe */
	MUTEX_CREATE( semaphore, status );
	ENSURES( cryptStatusOK( status ) );

	/* Initialize the mutexes */
	MUTEX_CREATE( mutex1, status );
	ENSURES( cryptStatusOK( status ) );
	MUTEX_CREATE( mutex2, status );
	ENSURES( cryptStatusOK( status ) );
	MUTEX_CREATE( mutex3, status );
	ENSURES( cryptStatusOK( status ) );

	return( CRYPT_OK );
	}

/*
 * Set the pred and succ of the given free block
 * Since the whole memory space is 2^32 bytes
 * I can compress the 8 bytes address into 4 bytes
 * by computing its offest to heap_listp
 */
static inline void set_ptr(uint32_t* const block, 
                          uint32_t* const pred_block, 
                          uint32_t* const succ_block) {
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));

    unsigned int pred_offest; 
    unsigned int succ_offest;

    if (pred_block == NULL)
        pred_offest = 0;
    else 
        pred_offest = pred_block - heap_listp;

    if (succ_block == NULL)
        succ_offest = 0;
    else
        succ_offest = succ_block - heap_listp;

    //printf("pred_off = %d, succ_off = %d\n", pred_offest, succ_offest);
    set_val(block + 1 , pred_offest);
    set_val(block + 2 , succ_offest);
    ENSURES(block_pred(block) == pred_block);
    ENSURES(block_succ(block) == succ_block);    
}

/*
 * Extends the heap with a new free block
 * Return: the pointer to the new free block 
 *         NULL on error.
 */
static void *extend_heap(unsigned int words) {
    REQUIRES(words > 4);

    uint32_t *block;
    uint32_t *next;
    

    /* Ask for 2 more words for header and footer */
    words = (words % 2) ? (words + 1) : words;
    if (VERBOSE)
        printf("Extend Words = %d bytes\n", words * 4);
    if ((long)(block = mem_sbrk(words * WSIZE)) == -1)
        return NULL;

    block--;          // back step 1 since the last one is the epi block
    set_size(block, words - 2);
    block_mark(block, FREE);

    ENSURES(block != NULL);
    // New eqilogue block
    next = block_next(block);    
    set_size(next, 0);
    *next |= 0x40000000;
    //block_mark(block_next(block), ALLOCATED);

    ENSURES(!block_free(next));
    ENSURES(block_size(next) == 0);
    block = coalesce(block);    // Coalesce if necessary
    ENSURES(in_list(block));
    return block;
 }

/*
 * Place the block and potentially split the block
 * Return: Nothing
 */
static void place(void *block, unsigned int awords) {
    REQUIRES(awords >= 2 && awords % 2 == 0);
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));
    REQUIRES(in_list(block));

    unsigned int cwords = block_size(block); //the size of the given freeblock
    block_delete(block);      // delete block from the seg list
    
    ENSURES(!in_list(block));

    if ((cwords - awords) >= 4) {
        set_size(block, awords);
        block_mark(block, ALLOCATED);
        block = block_next(block);
        set_size(block, cwords - awords - 2);
        block_mark(block, FREE);
        block_insert(block);

        ENSURES(in_list(block));
    } else {
        set_size(block, cwords);
        block_mark(block, ALLOCATED);
    }    
 }

	void* reserve_memory(size_t size)
	{
#ifdef _WIN32
		void* ret = VirtualAlloc(NULL, size, MEM_RESERVE, PAGE_NOACCESS);
		ENSURES(ret != NULL);
#else
		void* ret = mmap(nullptr, size, PROT_NONE, MAP_ANON | MAP_PRIVATE, -1, 0);
		ENSURES(ret != 0);
#endif
		return ret;
	}

queue *queue_new() {
  queue *Q = xmalloc(sizeof(queue));
  list *p = xmalloc(sizeof(list));
  /* Dummy node: does not need to be initialized! */
  Q->front = p;
  Q->back = p;

  ENSURES(is_queue(Q));
  ENSURES(queue_empty(Q));
  return Q;
}

// Return the header to the successor free block
static inline uint32_t* block_succ(uint32_t* const block) {
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));

    uint32_t * address = heap_listp + block[2];

    ENSURES(address != NULL);
    ENSURES(in_heap(address));

    if (address == heap_listp)
        return NULL;
    else 
        return address;
}

static int readGeneralInfo( INOUT STREAM *stream, 
							INOUT CMP_PROTOCOL_INFO *protocolInfo )
	{
	long endPos;
	int length, iterationCount, status;

	assert( isWritePtr( stream, sizeof( STREAM ) ) );
	assert( isWritePtr( protocolInfo, sizeof( CMP_PROTOCOL_INFO ) ) );

	/* Go through the various attributes looking for anything that we can
	   use */
	readConstructed( stream, NULL, CTAG_PH_GENERALINFO );
	status = readSequence( stream, &length );
	if( cryptStatusError( status ) )
		return( status );
	endPos = stell( stream ) + length;
	for( iterationCount = 0; 
		 stell( stream ) < endPos && \
			iterationCount < FAILSAFE_ITERATIONS_MED; iterationCount++ )
		{
		status = readGeneralInfoAttribute( stream, protocolInfo );
		if( cryptStatusError( status ) )
			return( status );
		}
	ENSURES( iterationCount < FAILSAFE_ITERATIONS_MED );

	return( status );
	}

static int findDnInGeneralName( INOUT CERT_INFO *certInfoPtr,
								const BOOLEAN updateCursor )
	{
	ATTRIBUTE_PTR *attributePtr;
	DN_PTR **dnPtr;
	int status;

	assert( isWritePtr( certInfoPtr, sizeof( CERT_INFO ) ) );

	/* We're inside a GeneralName, clear any possible saved selection */
	certInfoPtr->currentSelection.generalName = CRYPT_ATTRIBUTE_NONE;

	REQUIRES( sanityCheckSelectionInfo( certInfoPtr ) );

	/* Search for a DN in the current GeneralName */
	attributePtr = findDnInAttribute( certInfoPtr->attributeCursor );
	if( attributePtr == NULL )
		return( CRYPT_ERROR_NOTFOUND );

	/* We found a DN, select it */
	status = getAttributeDataDN( attributePtr, &dnPtr );
	if( cryptStatusError( status ) )
		return( status );
	certInfoPtr->currentSelection.dnPtr = dnPtr;
	if( updateCursor )
		certInfoPtr->attributeCursor = attributePtr;
	certInfoPtr->currentSelection.dnInExtension = TRUE;

	ENSURES( sanityCheckSelectionInfo( certInfoPtr ) );

	return( CRYPT_OK );
	}

// Returns a pointer if block of sufficient size is available 
// will allocate a new block if none are free
static void* find_free_block(int index, size_t size){
    REQUIRES(0 <= index && index < NUM_FREE_LISTS);

    void* block;
    void* current;
    int new_index = index; 

    while(new_index < NUM_FREE_LISTS){
    	current = free_lists[new_index];

    	while(current != NULL){
    		if(block_size(current) >= size){
    			// if(new_index > index){
    			// 	block = split_block(new_index);
    			// 	block_mark(block, 0);
    			// 	return block;
    			// }
    			block = current;
    			block_mark(block, 0);
    			remove_block_from_list(new_index, block);
    		}
    		current = block_next(current);
    	}
        new_index++;
    }
    assert(aligned(block));
    block = allocate_block(size);

    ENSURES(block != NULL);
    return block;
}

tree* tree_insert(tree* T, elem x, bst B)
{
  REQUIRES(is_tree(T, B));
  REQUIRES(x != NULL);

  if (T == NULL) {
    T = xmalloc(sizeof(tree));
    T->height = 1;
    T->data = x;
    T->left = NULL;
    T->right = NULL;
  } else {
    int r = B->elem_compare(x, T->data);
    if (r == 0) {
      T->data = x;
    } else if (r < 0) {
      T->left = tree_insert(T->left, x, B);
      T = rebalance_left(T, B);
    } else {
      T->right = tree_insert(T->right, x, B);
      T = rebalance_right(T, B);
    }
  }

  ENSURES(is_tree(T, B));
  return T;
}

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    REQUIRES(M > 0);
    REQUIRES(N > 0);

    ENSURES(is_transpose(M, N, A, B));
}

hostptr_t Buddy::get(size_t &size)
{
    REQUIRES(size > 0);
    hostptr_t ret = __impl::util::allocator::Buddy::get(size);
    ENSURES(ret == NULL || (ret >= addr_ && ret <= (addr_ + size_ - size)));
    return ret;
}

void sift_down(heap H, int i)
{
  REQUIRES(is_safe_heap(H));
  REQUIRES(H->next > 1 && is_heap_except_down(H, i));

  while (2*i < H->next)
  {
    ASSERT(1 <= i && i < H->next);
    ASSERT(is_heap_except_down(H, i));
    ASSERT(grandparent_check(H, i));
    int left = 2*i;
    int right = left + 1;
    if (ok_above(H, i, left)
        && (right >= H->next || ok_above(H, i, right))) {
      return;
    }
    else if (right >= H->next || ok_above(H, left, right)) {
      swap_up(H, left);
      i = left;
    }
    else {
      ASSERT(right < H->next && ok_above(H, right, left));
      swap_up(H, right);
      i = right;
    }
  }
  ASSERT(i < H->next && 2*i >= H->next);
  ASSERT(is_heap_except_down(H, i));
  ENSURES(is_heap(H));
}

static void *find_fit(size_t asize)

{
   /* First fit search */
  void* bp;
  //  print_list();
  int offset = get_offset(asize);
  //printf("in first fit search  \n");
  for (int i = offset; i < 9; i++)
    {
      //printf ("In bucket %d \n",i);
      for (bp =((void*) (*(long*)GET_BUCKET(root, i)));
           bp != NULL ; bp = get_succ(bp) )
        {
          // printf("bp %p \n",bp);
          REQUIRES ((void*)bp != NULL);
          REQUIRES (((size_t)(bp))%8 == 0);
          size_t size =  GET_SIZE(HDRP((bp)));
          if (!GET_ALLOC( HDRP(((bp) ) )) &&
              (asize <= size))
            {
              ENSURES ( (size_t)(bp)%8 == 0);
              size_t diff = size - asize;
              return first_best_fit((void*)bp,asize, diff) ;
            }
        }
    }
  return NULL; /* No fit */
}

CHECK_RETVAL_LENGTH \
int sizeofMessageDigest( IN_ALGO const CRYPT_ALGO_TYPE hashAlgo,
                         IN_LENGTH_HASH const int hashSize )
{
    const int hashParam = isParameterisedHashAlgo( hashAlgo ) ? hashSize : 0;
    int algoInfoSize, hashInfoSize;

    REQUIRES( isHashAlgo( hashAlgo ) );
    REQUIRES( hashSize >= 16 && hashSize <= CRYPT_MAX_HASHSIZE );

    algoInfoSize = sizeofAlgoIDex( hashAlgo, hashParam, 0 );
    hashInfoSize = sizeofObject( hashSize );
    ENSURES( algoInfoSize > 8 && algoInfoSize < MAX_INTLENGTH_SHORT );
    ENSURES( hashInfoSize > hashSize && hashInfoSize < MAX_INTLENGTH_SHORT );

    return( sizeofObject( algoInfoSize + hashInfoSize ) );
}

void *calloc (size_t nmemb, size_t size) {
  size_t bytes = nmemb * size;
  void *newptr;
  //printf ("calloc %d\n" ,(int)size);
  newptr = malloc(bytes);
  memset(newptr, 0, bytes);
  ENSURES ( (size_t)(newptr)%8 == 0);
  return newptr;
}

void enq(queue *Q, queue_elem x) {
  REQUIRES(is_queue(Q));

  Q->back->data = x;
  Q->back->next = xmalloc(sizeof(list));
  Q->back = Q->back->next;

  ENSURES(is_queue(Q) && !queue_empty(Q));
}

void
Mode::registerKernel(gmac_kernel_id_t k, KernelImpl &kernel)
{
    REQUIRES(kernels_.find(k) == kernels_.end());

    Parent::registerKernel(k, kernel);

    ENSURES(kernels_.find(k) != kernels_.end());
}

elem bst_lookup(bst B, elem x)
{
  REQUIRES(is_bst(B) && x != NULL);

  elem r = tree_lookup(B->root, x, B);

  ENSURES(r == NULL || B->elem_compare(r, x) == 0);
  return r;
}