//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//
//
// Use of this source code is subject to the terms of the Microsoft end-user
// license agreement (EULA) under which you licensed this SOFTWARE PRODUCT.
// If you did not accept the terms of the EULA, you are not authorized to use
// this source code. For a copy of the EULA, please see the LICENSE.RTF on your
// install media.
//
/*++


Module Name:

    usb2lib.cpp

Abstract:

    interface to usb2lib, usb2 low/full speed scheduling algorithms

Environment:

    kernel or user mode only

Notes:

Revision History:

--*/
#include <windows.h>
#include "usb2lib.h"

TransactionTrasnlate::TransactionTrasnlate (const UCHAR uHubAddress,const UCHAR uPort,TransactionTrasnlate * pNextTT)
    : m_uHubAddress(uHubAddress)
    , m_uPort(uPort)
{
    m_pNextTT =  pNextTT;
    m_dwThink_time =1;
    for (DWORD dwIndex=0; dwIndex<MAXFRAMES; dwIndex++) {
        TT_frame[dwIndex]=NULL;
        frame_budget[dwIndex].time_used=0;;
    }
}
TransactionTrasnlate::~TransactionTrasnlate ()
{
    for (DWORD dwIndex=0; dwIndex<MAXFRAMES; dwIndex++) {
        LPEndpointBugetList pCurList = TT_frame[dwIndex];
        if (pCurList!=NULL) {
            LPEndpointBugetList pNextList = pCurList ->pNextEndpt;
            delete pCurList;
            pCurList = pNextList;
        }
        TT_frame[dwIndex]=NULL;
    }
};
BOOL TransactionTrasnlate::AddedEp(LPEndpointBuget ep)
{
    BOOL bReturn = TRUE;
    if (ep) {
       // split or nonsplit FS/LS speed allocation
        // classic allocation
        // split allocation
        unsigned int min_used = frame_budget[0].time_used;

        if (ep->period > MAXFRAMES)
        	ep->actual_period = MAXFRAMES;
        else
        	ep->actual_period = ep->period;

        // Look at all candidate frames for this period to find the one with min
        // allocated bus time.  
        //
        for (unsigned int i=1; i < ep->actual_period ; i++) {
            if (frame_budget[i].time_used < min_used) {
                min_used = frame_budget[i].time_used;
                ep->start_frame = i;
            }
        }
        //***
        //*** 2. Calculate classic time required
        //***

        // Calculate classic overhead
        DWORD overhead;
        if (ep->ep_type == isoch) {
            if (ep->speed == FSSPEED)
                overhead = FS_ISOCH_OVERHEAD + m_dwThink_time;
            else {
                ASSERT(FALSE);
                return FALSE;
            }
        } 
        else  { // interrupt
            if (ep->speed == FSSPEED)
                overhead = FS_INT_OVERHEAD + m_dwThink_time;
            else
                overhead = LS_INT_OVERHEAD + m_dwThink_time;
        }

        // Classic bus time, NOT including bitstuffing overhead (in FS byte times) since we do best case budget
        ep->calc_bus_time = (USHORT)(ep->max_packet * (ep->speed!=LSSPEED?1:8) + overhead);

        USHORT latest_start = FS_SOF + HUB_FS_ADJ;  // initial start time must be after the SOF transaction

        for (i=0; ep->start_frame + i < MAXFRAMES && bReturn==TRUE; i += ep->actual_period) {
            DWORD t=0;
            if (FindBestTimeSlot(latest_start,ep->calc_bus_time,TT_frame[ep->start_frame + i],&t)) {
                ASSERT(t>=latest_start);
                // update latest start time as required
                if (t > latest_start)
                    latest_start = (USHORT)t;
            }
            else { // Runout the slot this one.
                ASSERT(FALSE);
                ep->calc_bus_time = 0;
                bReturn= FALSE;
                break;
            }
        } // end of for loop looking for latest start time

        if (bReturn==TRUE) {
            // Set the start time for the new endpoint
            ep->start_time = latest_start;

            if ((ep->start_time + ep->calc_bus_time) > FS_MAX_PERIODIC_ALLOCATION)  {
            //		error("start time %d past end of frame", ep->start_time + ep->calc_bus_time);
                ep->calc_bus_time = 0;
                return FALSE;
            }
            BOOL bRet=TRUE;
            for (i=0; ep->start_frame + i < MAXFRAMES; i += ep->actual_period) {
                bRet &= InsertEp(ep->start_frame + i, ep);
                ASSERT(bRet==TRUE);
                frame_budget[0].time_used += ep->calc_bus_time;
            }
            if (bRet == FALSE) {
                for (i=0; ep->start_frame + i < MAXFRAMES; i += ep->actual_period) {
                    RemoveEp(ep->start_frame + i, ep);
                    frame_budget[0].time_used -= ep->calc_bus_time;
                }
            }
            bReturn = bRet;
        }

    }
    ASSERT(bReturn);
    return bReturn;
}
BOOL  TransactionTrasnlate::DeletedEp(LPEndpointBuget ep)
{
    BOOL bReturn = TRUE;
    for (unsigned int i=0; ep->start_frame + i < MAXFRAMES; i += ep->actual_period) {
        if (RemoveEp(ep->start_frame + i, ep))
            frame_budget[0].time_used -= ep->calc_bus_time;
        else{
            ASSERT(FALSE);
            bReturn=FALSE;
        }
    }
    return bReturn;    
}

BOOL TransactionTrasnlate::FindBestTimeSlot(USHORT start_time,USHORT time_duration,LPEndpointBugetList lpList,PDWORD pdwReturn)
{
    while (lpList) {
        // Check this is no overlap.
        if (lpList->endpt.start_time  >= start_time +  time_duration) { // Empty Slot has been found.
            break;
        }
        else if (lpList->endpt.start_time +  lpList->endpt.calc_bus_time <= start_time) { // Have not reach yet . Continue
            lpList = lpList ->pNextEndpt;
        }
        else { // We have overlap. Let us move slot later.
            start_time = lpList->endpt.start_time +  lpList->endpt.calc_bus_time;
            lpList =  lpList ->pNextEndpt;
        }
    }
    *pdwReturn = start_time;
    return TRUE;
}
BOOL TransactionTrasnlate::InsertEp(DWORD frameIndex,LPEndpointBuget ep)
{
    if (frameIndex>=MAXFRAMES || ep == NULL) {
        ASSERT(FALSE);
        return FALSE;
    }
    BOOL bReturn = FALSE;
    EndpointBugetList * pNewEpList = new EndpointBugetList;
    if (pNewEpList) {
        pNewEpList->endpt = *ep;
        // find out where is not
        EndpointBugetList * pPrevNode=NULL;
        EndpointBugetList * pCurNode = TT_frame[frameIndex];
        bReturn = TRUE;
        while (pCurNode) {
            if (pCurNode->endpt.start_time +  pCurNode->endpt.calc_bus_time <= ep->start_time) { // Continue
                pPrevNode = pCurNode;
                pCurNode =pCurNode->pNextEndpt;
            }
            else if (pCurNode->endpt.start_time >= ep->start_time+ep->calc_bus_time) { // Find hole
                bReturn=TRUE;
                break;
            }
            else {// This is really bad. Someone try to inserted something that has overlap.
                ASSERT(FALSE);
                bReturn = FALSE;
                break;
            }
        }
        if (bReturn) { // We reached last one.
            if (pPrevNode) { // Not first.
                pNewEpList->pNextEndpt = pPrevNode ->pNextEndpt;
                pPrevNode->pNextEndpt = pNewEpList;
            } else { // This is first.
                pNewEpList->pNextEndpt = TT_frame[frameIndex];
                TT_frame[frameIndex] = pNewEpList;
            }
        }
        else // Fails we have to clean it.
            delete pNewEpList;
    }
    return bReturn;
};
BOOL TransactionTrasnlate::RemoveEp(DWORD frameIndex,LPEndpointBuget ep)
{
    if (frameIndex>=MAXFRAMES || ep == NULL) {
        ASSERT(FALSE);
        return FALSE;
    }
    BOOL bReturn=FALSE;
    EndpointBugetList * pPrevNode=NULL;
    EndpointBugetList * pCurNode = TT_frame[frameIndex];
    while (pCurNode) {
        if (pCurNode->endpt.start_time +  pCurNode->endpt.calc_bus_time <= ep->start_time) { // Continue
            pPrevNode = pCurNode;
            pCurNode =pCurNode->pNextEndpt;
        }
        else if ( pCurNode->endpt.start_time == ep->start_time && pCurNode->endpt.calc_bus_time == ep->calc_bus_time) {
            bReturn=TRUE;
            break;
        }
        else { // Either overlap or behind, We can not find this one.
            bReturn=FALSE;
            break;            
        }
    };
    if (bReturn == TRUE && pCurNode!=NULL) {
        if (pPrevNode) // Not first one.
            pPrevNode->pNextEndpt=pCurNode->pNextEndpt;
        else
            TT_frame[frameIndex]= pCurNode->pNextEndpt;
        delete pCurNode;
    }
    else
        ASSERT(FALSE);
    return bReturn;

}

USB2lib::USB2lib()
{
    // allocate at TT to test with
    //myHC.tthead = (PTT) malloc(sizeof(TT));
    Lock();
    pTTRoot = NULL;
    thinktime = HS_HC_THINK_TIME;
    allocation_limit = HS_MAX_PERIODIC_ALLOCATION;
    speed = HSSPEED;

    for (int i=0; i<MAXFRAMES; i++) {
        for (int j=0; j < MICROFRAMES_PER_FRAME; j++) {
            HS_microframe_info[i][j].time_used = 0;
        }
    }
    Unlock();
}
USB2lib::~USB2lib()
{
    Lock();
    TransactionTrasnlate * pCurTT= pTTRoot;
    while (pCurTT) {
        TransactionTrasnlate * pNextTT = pCurTT->GetNextTT();
        delete pCurTT;
        pCurTT = pNextTT;
    }
    Unlock();
}
BOOL USB2lib::AddedTt( UCHAR uHubAddress,UCHAR uPort)
{
    BOOL bReturn = FALSE;
    Lock();
    if (GetTT( uHubAddress,uPort) == NULL) {
        TransactionTrasnlate * pNewTT = new TransactionTrasnlate(uHubAddress,uPort, pTTRoot);
        if ( pNewTT) {
            pTTRoot=pNewTT;
            bReturn=TRUE;
        }
    }
    else
        bReturn=TRUE;
    Unlock();
    return bReturn;
        
}
BOOL USB2lib::DeleteTt( UCHAR uHubAddress,UCHAR uPort)
{
    BOOL bReturn = FALSE;
    Lock();
    TransactionTrasnlate * pPrevTT= NULL;
    TransactionTrasnlate * pCurTT = pTTRoot;
    while ( pCurTT!=NULL ) {
        if (pCurTT->GetHubAddress()==uHubAddress && pCurTT->GetHubPort() == uPort)
            break;
        else {
            pPrevTT = pCurTT;
            pCurTT = pCurTT->GetNextTT();
        }
    }
    if (pCurTT) { // We found one matched.
        if (pPrevTT) { // Not First One.
            pPrevTT ->SetNextTT(pCurTT->GetNextTT());
            delete pCurTT;
        }
        else { // First one
            pTTRoot = pCurTT->GetNextTT();
            delete pCurTT;
        }
        bReturn=TRUE;
     }
    Unlock();
    return bReturn;
}
TransactionTrasnlate * USB2lib::GetTT( const UCHAR uHubAddress,const UCHAR uHubPort)
{
    Lock();
    TransactionTrasnlate * pFoundTT = pTTRoot;
    while (pFoundTT) {
        if (pFoundTT->GetHubAddress() == uHubAddress && pFoundTT->GetHubPort() == uHubPort)
            break;
        else
            pFoundTT = pFoundTT->GetNextTT();
    }
    Unlock();
    return pFoundTT;
}

unsigned USB2lib::Add_bitstuff(unsigned bus_time) const
{
	// Bit stuffing is 16.6666% extra.
	// But we'll calculate bitstuffing as 16% extra with an add of a 4bit
	// shift (i.e.  value + value/16) to avoid floats.
	return (bus_time + (bus_time>>4));
}